Project Euler asks us to find the largest prime factor of the number 600851475143.

The following code is fairly straightforward and probably The Simplest Thing That Could Possibly Work. It's called Trial division.

def factorise(n):
    results = []

    check = 2
    while check ** 2 <= n:
        if not n % check:
            n /= check
            results.append(check)
        else:
            check += 1

    if n > 1: results.append(n)

    return results

Note that we don't actually have to worry about prime numbers. The fact that every positive integer greater than one has a unique prime factorization and we start with a prime number (2) ensures the following divisables will be prime numbers too. Also we will only have to check up to the square root of n after which the factor will re-cycle.

Using this and finding the largest prime factor in python is as easy as:

max(factorise(600851475143))

Update: based on some of the feedback I got, I decided to not publish any Project Euler solutions any more.

blog comments powered by Disqus