Project Euler Solution 3: Largest prime factor

This is another post in the Project Euler series, about Problem 3: Largest prime factor where we shall find the largest prime factor in a large number.

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

What is the largest prime factor of the number 600851475143?

First we need a generator for prime numbers. It is written quite simply. We go through the numbers and check all prime numbers found so far as factors. If we find a divisor, this number is not a prime number and we go to the next number. If we could go through all known prime factors and did not find a divisor, the new number is a prime number.

def prime_generator() -> int:
    primes = []
    for candidate in itertools.count(2):
        for prime in primes:
            if candidate % prime == 0:
                break
        else:
            yield candidate
            primes.append(candidate)

Now we can write a naive implementation for the number 13195. We just iterate through all primes up to that number and then remember the biggest prime factor that we have found.

number = 13195


def solution_naive() -> int:
    factor = None
    for prime in prime_generator():
        if number % prime == 0:
            factor = prime
        if prime > number:
            break
    return factor

Running this gives us the result 29, which we know from the problem statement. It took 49 ms to compute that.

Trying to run this with the actual number of 600,851,475,143, we have a problem. It doesn’t find a solution within a few seconds, so clearly this is not the intended solution.

A better way is to divide out the prime factors as we find them. This will reduce the problem size as we go. This is a slightly changed solution where we always reduce the remainder until the given prime is no longer a divisor.

def solution_reducing() -> int:
    remainder = number
    last_factor = None
    for prime in prime_generator():
        while remainder % prime == 0:
            last_factor = prime
            remainder /= prime
        if remainder == 1:
            break
    return last_factor

With the small number it only takes 5 µs, so it is a factor 10,000 faster than the naive version. And with the actual number we get a result of 6,857 in just 16 ms, which seems fast enough.