最大公約数を求める

質問

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

回答No.3

zk43

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

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