読者です 読者をやめる 読者になる 読者になる

Project Euler #003 - 素因数分解

問題

13195 の素因数は 5、7、13、29 である。

600851475143 の素因数のうち最大のものを求めよ。

方針

m/n=q:mをnで除して余が0である場合はその素数は素因数の一つ。

nを最小の素数である2から始めて、剰余が0かつ除算の答えqがn以上である間、nで割り切り続ける。

剰余が0でなくなったらnを素因数として保存、次の除数n=n+1で同様に割り続ける。

除算の答えqが除数より小さくなったら終了。

最後の答えqが0でない場合は最後の素因数として保存する。

感想

中学で習った素因数分解と同じ理屈。速度は遅いけどわかりやすさ優先で。

ていうか他の方法知らないし。

 

回答