この記事の所要時間： 約 0分48秒
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 2 3 4 5 6 7 |
N = 600851475143 n = 1 while N > 1: n += 2 while N % n == 0: N /= n print n |
