Largest prime factor Problem 3 The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?



In [12]:

    
def is_prime(n):
    if n == 2:
        return True
    if (n < 2) or (n % 2 == 0):
        return False
    return all(n % i for i in range(3, int(sqrt(n)) + 1, 2))



In [2]:

    
n=600851475143



In [14]:

    
next((x for x in range(int(sqrt(n)), 1, -1) if n%x==0 and is_prime(x)), None)









    Out[14]:





6857



In [15]:

    
%timeit next((x for x in range(int(sqrt(n)), 1, -1) if n%x==0 and is_prime(x)), None)









    



10 loops, best of 3: 106 ms per loop



In [18]:

    
max(x for x in range(2, int(sqrt(n))) if n%x==0 and is_prime(x))









    Out[18]:





6857



In [19]:

    
%timeit max(x for x in range(2, int(sqrt(n))) if n%x==0 and is_prime(x))









    



10 loops, best of 3: 110 ms per loop