プロジェクトオイラー3.

この記事の所要時間: 048

No.3 Largest prime factor

問題.

Q. 13195 の素因数は, 5, 7, 13, 29 です. (\(13195=5\times7\times13\times29\)).

では, 600851475143 の素因数で最大のものは?

考え方とプログラム例(Python)

1. 小さい数で順に割っていく

与えられた 600851475143 を, \(n=2, 3, 4, \ldots\) で順に割っていき, 最後に割った商が1になったときの \(n\) が最大の素因数になることを用います.

ただし, 600851476143 は明らかに奇数なので, これを割り切る素因数 \(n\) も必ず奇数となることを利用します.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加