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

この記事の所要時間: 10

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 も必ず奇数となることを利用します.

計算時間 1.92\times 10^{-3} 秒で解けました.

答えはこの下の行にあります. 反転してください.

A. 6857

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