Project Euler: Problem 7, redux

Remember how I mentioned the Sieve wasn't the most performant solution? Here's a much faster solution. On my system the time dropped from 11.661 seconds to .332 seconds. Also, it makes use of one of my favorite features in Python, so far: generators.

"""Solves Problem 7 from Project Euler."""

import math
import sys

def is_prime(candidate, known_primes):
    """Determines whether candidate is prime by trial division using \

    For this function to work, known_primes *must* be accurate.
    last_possible = math.sqrt(candidate)
    for current_prime in known_primes:
        if current_prime > last_possible:
        if not candidate % current_prime:
            return False
    return True

def primes_generator():
    """A generator for all the primes <= sys.maxint."""
    candidates = xrange(2, sys.maxint)
    primes = []
    for n in candidates:
        if is_prime(n, primes):
            yield n

def problem_7(n):
    """Finds the nth prime number."""
    primes = primes_generator()
    i = 0
    while i < n - 1:
        i += 1

    return primes.next()

if __name__ == '__main__':
    print problem_7(10001)

Back to flipping out...

blog comments powered by Disqus