質問: 最大公約数を求める 一般に、a,bが2^nくらいの整数であれば、最大公約数を求めるには、割り算も含めてn^3に比例した計算量が必要であるといわれている。しかし、これを素因数分解して求めると、素因数分解するのに、その数の平方根までの割り算が必要になるので、(√2)^nに比例した計算量が必要になる。 という説明があったのですが、”素因数分解するのに、その数の平方根までの割り算が必要になる”というのがよく分かりません。何故平方根まで割り算しないとならないのでしょうか????
回答: 単純に 2で割る、3で割る、4で割る、... と繰り返して、素因数を見付けるのに、最悪 [√a] まで作業を繰り返す必要があるから。