プロジェクトオイラー3. ~ Largest prime factor ~

No.3 Largest prime factor

問題.

Q. 13195 の素因数は, 5, 7, 13, 29 です. ().

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

 

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

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

与えられた 600851475143 を, で順に割っていき, 最後に割った商が1になったときの が最大の素因数になることを用います.

ただし, 600851476143 は明らかに奇数なので, これを割り切る素因数 も必ず奇数となることを利用して少しだけ手間を省きます．

N = 600851475143
n = 1
while N > 1:
    n += 2
    while N % n == 0:
        N /= n
print(n)