この記事の所要時間: 約 1分0秒
No.3 Largest prime factor
問題.
Q. 13195 の素因数は, 5, 7, 13, 29 です. ().
では, 600851475143 の素因数で最大のものは?
考え方とプログラム例(Python)
1. 小さい数で順に割っていく
与えられた 600851475143 を, で順に割っていき, 最後に割った商が1になったときの
が最大の素因数になることを用います.
ただし, 600851476143 は明らかに奇数なので, これを割り切る素因数 も必ず奇数となることを利用します.
1 2 3 4 5 6 7 |
N = 600851475143 n = 1 while N > 1: n += 2 while N % n == 0: N /= n print n |
計算時間 秒で解けました.
答えはこの下の行にあります. 反転してください.
A. 6857