[Project Euler] Problem 3

원문: Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

13195 의 소인수는 5, 7, 13, 29 이다.
600851475143 의 가장 큰 소인수는 무엇인가?

Python

>>> import math
>>> def isprime(num) :
    if num%2 == 0 :
        if num == 2 :
            return True
        else :
            return False
    for k in range(3, int(math.sqrt(num))+1, 2) :
        if num%k == 0 :
            return False
    else :
        return True
>>> n = 600851475143
>>> while n != 1 :
    for k in filter(isprime, range(3, int(n+1), 2)) :
        if n%k == 0 :
            n /= k
            break
else :
    print(k)

접기

ps.
좀 더 좋은 알고리즘 없나요? 시간은 7.15255737305e-06 초 정도 나오긴 했는데.