The Home for People Who Like to Flip Out and Write Code
Project Euler: Problem 7
My new math trick of the day? Upper and lower bounds on the nth prime:
Using this little nugget, I can give myself an upper bound on the
numbers I need to test for primality and unleash the Sieve of
Eratosthenes on Problem 7. Yes, I realize the Sieve isn’t
the most performant way to do most of these tests; I just think it’s
a really elegant solution for finding primes and it isn’t slow enough
to be an issue for most numbers of this size. At any rate, here’s my
script:
"""Solves Problem 7 from Project Euler."""importmathFIRST_SIX_PRIMES={1:2,2:3,3:5,4:7,5:11,6:13}defe_sieve(upper_bound):"""Uses the Sieve of Eratosthenes to get a list of the primes up to max."""primes=[]candidates=range(2,upper_bound)whilecandidates:head=candidates[0]primes.append(head)candidates=[nfornincandidates[1:]ifn%head]returnprimesdefproblem_7(n):"""Finds the nth prime number. Thanks to http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number we know that it will be less than n * ln(n) + n * ln(ln(n)) (for n >= 6). """ifn<6:returnFIRST_SIX_PRIMES[n]upper_bound=int(n*math.log(n)+n*math.log(math.log(n)))primes=e_sieve(upper_bound)returnprimes[n-1]if__name__=='__main__':printproblem_7(10001)