The Home for People Who Like to Flip Out and Write Code
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."""importmathimportsysdefis_prime(candidate,known_primes):"""Determines whether candidate is prime by trial division using \ known_primes. For this function to work, known_primes *must* be accurate. """last_possible=math.sqrt(candidate)forcurrent_primeinknown_primes:ifcurrent_prime>last_possible:breakifnotcandidate%current_prime:returnFalsereturnTruedefprimes_generator():"""A generator for all the primes <= sys.maxint."""candidates=xrange(2,sys.maxint)primes=[]fornincandidates:ifis_prime(n,primes):primes.append(n)yieldndefproblem_7(n):"""Finds the nth prime number."""primes=primes_generator()i=0whilei<n-1:i+=1primes.next()returnprimes.next()if__name__=='__main__':printproblem_7(10001)