Project Euler: Problem 3

I just finished playing around with Problem 3 from Project Euler. My rough idea for the problem was to build a list of the primes up to the number in question and start testing them, since I already knew the basics of the Sieve of Eratosthenes and I didn't know any good algorithms for factoring. After I finished, I looked up some of those algorithms (see Wikipedia's (incomplete) list), and I probably wouldn't have bothered with anything that complex anyway. Here's my original "solution" (I use scare quotes since I know it has bugs, and I knew it at the time).

"""Solves Problem 3 from Project Euler."""

import math

def e_sieve(upper_bound):
    """Uses the Sieve of Eratosthenes to get a list of the primes up to max."""
    primes = []
    candidates = range(2, upper_bound)
    while candidates:
        head = candidates[0]
        candidates = [n for n in candidates[1:] if n % head]

    return primes

def find_highest_prime_factor(to_factor):
    """Find the highest prime factor of to_factor."""
    highest_prime = None
    primes = e_sieve(int(math.sqrt(to_factor)))
    for prime in primes:
        if not to_factor % prime:
            quotient = to_factor / prime
            if quotient in primes:
                return quotient
            highest_prime = prime

    if highest_prime:
        return highest_prime

    return to_factor

if __name__ == "__main__":
    print find_highest_prime_factor(600851475143)

After I coded up my solution and verified I had the right answer (after what seemed like forever but was really ~15 minutes), I just knew there had to be a faster way. A little work with cProfile quickly revealed I was spending all my time in the Sieve. It turns out that even a "naïve" algorithm for factoring is better than generating the primes for a number this size. My new, "naïve" solution ran in 44 ms.

"""Solves Problem 3 from Project Euler."""

def factorize(to_factor):
    """Use trial division to factorize to_factor and return all the resulting \
    factors = []
    divisor = 2
    while (divisor < to_factor):
        if not to_factor % divisor:
            to_factor /= divisor
            # Note we don't bump the divisor here; if we did, we'd have
            # non-prime factors.
        elif divisor == 2:
            divisor += 1
            # Trivial optimization: skip even numbers that aren't 2.
            divisor += 2
    if not to_factor % divisor:
        # Don't forget the last factor
    return factors

if __name__ == "__main__":
    print max(factorize(600851475143))

As an added bonus, this code has fewer bugs. One of these days, I'll learn to follow KISS. One of these days….

Back to flipping out...

blog comments powered by Disqus