最も大きな素因数

Project Euler 3

13195の素因数は 5, 7, 13 そして 29 である。
600851475143 の最大の素因数は何か？

---

以下、記載を簡略化するため N = 600851475143 とする。

N は C long 型を超過しているため、range(2, N) とすると OverflowError が発生する。

$\lfloor\sqrt{N}\rfloor$ を超える素因数は高々1個しか存在しないため、まず 2 から $\lfloor\sqrt{N}\rfloor$ までの素因数を算出する。
N を算出された素因数で除算したのち、残った値が「高々1個の素因数」になる。

以下のサンプルでは、素因数とべき乗数を辞書として格納している。

# SAMPLE_1
from math import sqrt

N = 600851475143
l = range(2, int(sqrt(N)) + 1)

ans = {}
for i in l:
    while N % i == 0:
        N /= i
        try:
            ans[i] += 1
        except KeyError:
            ans[i] = 1
if N > 1:
    ans[N] = 1
print sorted(ans.keys(), reverse=True)

一応、2 と奇数のみで除算する仕組みも考慮したが、この程度の値であればあまり大した差異は見受けられなかった。
より大きな数値であれば計算量が半分になっているため、以下のコードが効果的に機能するかもしれない。

# SAMPLE_2
from math import sqrt

N = 600851475143
ans = {}

while N % 2 == 0:
    N /= 2
    try:
        ans[2] += 1
    except KeyError:
        ans[2] = 1

stop = int(sqrt(N)) + 1
i = 3
while(i < stop):
    while N % i == 0:
        N /= i
        try:
            ans[i] += 1
        except KeyError:
            ans[i] = 1
    i += 2
if N > 1:
    ans[N] = 1
print sorted(ans.keys(), reverse=True)