素因数分解

$a$, $b$ を自然数とするときその最大公約数 (Greatest Common Divisor, GCD) とは, $a$ と $b$ を共に割り切る数で最大のものである. この数は $a$ と $b$ を素因数分解すれば求まるが, 実は素因数分解で GCD を求めるのは効率がわるい. この章では, GCD 計算の高速アルゴリズムである Euclid の互除法を 説明し, あわせて計算の効率を議論する計算量 (computational complexity) の理論への入門を試みる.

例題 7.1   入力された自然数 $n$ の素因数分解を求めよ.

def prime_factorization(N) {
   K = 2;
   while (N>=2) {
     if (N % K == 0) {
        N = idiv(N,K);
        print(K,0); print(", ",0);
     }else{
        K = K+1;
     }
   }
   print(" ");
}

    

N % K は N を K で割った 余り. idiv(N,K) は N を K で割ったときの 商をあらわす. このプログラムでは, K で試しに N をわってみて 割り切れたら, 因子として出力する.

N が 60 の時の変数の変化:

K	2	2	$\cdots$
N	60	30	$\cdots$
行番号	3と4の間	3と4の間	$\cdots$

問: この表を完成し, プログラムの動きを説明せよ.