Project Euler: Problem 3

http://projecteuler.net/index.php?section=problems&id=3

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

What is the largest prime factor of the number 600851475143 ?

Prime factorization should be easy, right? I started with some old code I had (which was probably stolen off the Internet some time in the past):

def f1(n):
    factors = []
    last = n

    if n <  1: return 0
    if n == 1: return 1

    while last != 1:
        c = 2

        while last % c != 0:
            c += 1

        factors.append(c)
        last /= c

    return max(factors)

So far so good; it gets us the right answer. Look at those nasty inefficiencies, though. Specifically, we always start our search with 2 even after we've determined there are no more factors of two left. Also, after 2 we should only check odd candidates. Let's try again:

def f2(n):
    factors = []
    last = n

    if n <  1: return 0
    if n == 1: return 1

    while last != 1:
        try:
            c = factors[-1]
        except:
            c = 2

        while last % c != 0:
            if c==2:
                c += 1
            else:
                c += 2

        factors.append(c)
        last /= c

    return max(factors)

Much better! On my set-up, f1(600851475143) returns in about 3.14e-03 seconds. The better optimized version, f2(600851475143), returns in about 1.24e-03 seconds. We might be able to do better still if we first create a list of prime numbers (up to sqrt(n)) and only use those as possible candidates. I might try that later.