Project Euler problem 3

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.

It reminds me a bit of the famous greedy algorithm example of dividing an amount into a combination of coins, though it's not actually the same thing.

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))