Problem 3:

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

What is the largest prime factor of the number 600851475143 ?

A solution:

We can use the factorize function written for Problem 5, but it needs to be modified. The number to be factored is so large that the upper limit of numbers that need to be checked as factors is of type long, rather than of type int. The range() function doesn’t like numbers that large (unsurprisingly, as that would be a very very very long list to store), so a while loop needs to be used instead of a for loop.

def factorize(num):
    powers = []
    limit = (num/2)+1
    i = 2
    while i <= limit:
        while num % i == 0: # ie, i is a factor of num
            powers.append(i)
            num = num/i
        i += 1
        if num == 1: break  # ie, all factors have been found
    if len(powers) == 0: powers.append(num)  # num is prime
    return powers

This function can then be used to find the prime factors of the given number.

There are ways this method can be improved: if the factor 2 is handled separately before the while loop, then the loop only needs to be done for odd numbers, using half of the iterations. As well, a separate function that tests for primality could be called at the beginning: since a prime test only needs to check up to sqrt(number) instead of number/2, it can be a lot faster to know if the number itself is prime, rather than trying to find all of its factors.