Problem 3 「最大の素因数」 †
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
解法
ｂ=600851475143とします。
2,3,4,5,,,,
と小さい数から1ずつ増加させこの数をaとしましてaでｂを割り切れるか試します。
割り切れるなら割り切れる限りその数でbを割り、割った数を再度ｂとしまたaを１ずつ増加させて割り切れるかためしこれを繰り返します。
これにより素数による割り切りだけが残ります。
もしa^2>bとなったら最後に割り切った数とbのうち大きなほうが答えとなります。
なぜここで答えを出してよいかというと。
bがaより大きな数cで割り切れたとします。
するとb/c=d ｄは自然数と定義できます。
b=cdで
bはｄでも割り切れることが判明します。
ｃは√ｂより大きいのでｄは√ｂより小さくなります。
するとここまでの計算でｄによる割り切りは行われているはずです。
また割り切りの原理を具体例で考えてみましょう。
b=120=2*2*2*3*5
を割り切る場合を考えてみましょう。
最初２で割るので
b=15=3*5
3で割り切って
b=5
5が最大の答えとなります。
aが増加して素因数にぶち当たったらbの右側の素因数aが全部消えます。
そしてaより大きな素因数をaが消すことはありません。
素因数は素数ですので、aより大きな素数はaで割り切れないからです。
最終更新：2014年01月09日 08:47
