Euler Problem 3: Largest prime factor

Problem statement

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

What is the largest prime factor of the number 600851475143 ?

Solution

Define a function that calculates the first factor of the number



In [3]:

    
def factor(N):
    for i in xrange(2,N):
        if (N % i == 0):
            return i
    return 0

Once the first factor is calculated, the same factor function is applied to the result of dividing N by that factor It is iterated until all the factors are obtained



In [20]:

    
N = 600851475143
f = factor(N)
lf = []
while f > 0:
    lf.append(f)
    N = N / f
    #print("Factor: {}, Rest: {}".format(f, N)) #-- Debuging
    f = factor(N)
    
lf.append(N)
print("Factors:{}".format(lf))









    



Factors:[71, 839, 1471, 6857]

The solution is the maximum factor



In [22]:

    
print("Solution: {}".format(max(lf)))









    



Solution: 6857



In [26]:

    
factor(90709)









    Out[26]:





0



In [25]:

    
f = [11]
N = 997799 / 11



In [ ]: