最大公約数を求める

質問

一般に、a,bが2^nくらいの整数であれば、最大公約数を求めるには、割り算も含めてn^3に比例した計算量が必要であるといわれている。しかし、これを素因数分解して求めると、素因数分解するのに、その数の平方根までの割り算が必要になるので、（√２）^nに比例した計算量が必要になる。
という説明があったのですが、”素因数分解するのに、その数の平方根までの割り算が必要になる”というのがよく分かりません。何故平方根まで割り算しないとならないのでしょうか？？？？

回答No.2

sacra_sak · ベストアンサー

簡単な数字で約数を考えてみてください．たとえば 96 では，約数は，
　　　1，2，3，4，6，8，12，16，24，32，48，96
の 12 個です．そしてこれを両端から選んでいくと，積が元の数に一致することはご存知でしょう．つまり，
　　　1×96 = 96，
　　　2×48 = 96，
　　　3×32 = 96，……．
といったようにです．だからまず小さい約数 1 が分かれば 96 も約数だと分かります．2 が見つかれば 48 もそうです．3 が約数だから 32 もそうだ，という具合で，全部見つかるわけです．今回の場合は 1, 2, 3, 4, 6, 8 まで見つかれば，もう片方も決まるから，この六個だけの試験で約数が全部見つかったわけです．
さて小さいほうから 8 まで六個だけ見つければいいことは理解いただけたと思います．実はその「どこまで探せばよいか」が平方根となっていることにお気づきでしょうか．√96 はだいたい 9.80 ですが，真ん中の 8 と 12 の間にあります．つまり，
　　　1，2，3，4，6，8　| √96 ｜ 12，16，24，32，48，96
のように真ん中が平方根で，8 と 12，6 と 16，というふうに全部が対になっているから，平方根の手前の自然数 9 まで確認すれば大丈夫だということです．だってそれ以降はもう見つかっているんですから．
どの自然数でも約数を見つける際に同じような具合でできますから，平方根 (の一歩手前) まで割り算をすればいいのです．

回答No.3

zk43

自然数nが合成数として、n=abと自然数の積で表わされるとする。
a≦bとすると、n≧aa=a^2より、√n≧a
すなわち、nは必ず√n以下の素因数を持つ。
√n以下の数で割り切れなければ、nは素数である。

というような意味かと思うのですが。

回答No.1

koko_u_

単純に 2で割る、3で割る、4で割る、… と繰り返して、素因数を見付けるのに、最悪 [√a] まで作業を繰り返す必要があるから。