next up previous contents index
: 計算量 : ユークリッドの互除法とその計算量 : ユークリッドの互除法とその計算量   目次   索引

素因数分解

$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 NK で割った 余り. idiv(N,K)NK で割ったときの 商をあらわす. このプログラムでは, K で試しに N をわってみて 割り切れたら, 因子として出力する.

N が 60 の時の変数の変化:
K 2 2 $\cdots$
N 60 30 $\cdots$
行番号 3と4の間 3と4の間 $\cdots$

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




Nobuki Takayama 平成15年9月12日