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

この記事の所要時間：約 1分0秒

No.3 Largest prime factor

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

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

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

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

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

N = 600851475143

n = 1

while N > 1:

n += 2

while N % n == 0:

N /= n

print n

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

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

A. 6857