Wednesday, August 27, 2008

Problem 7: FInd 10001st prime

# The number of primes less than a number x converges to 1n(x)/x.
# I initially estimated that the 10001st prime would be less than 100000.
# That later turned out to be false and I increased the estimate to 200000.
# Using the Sieve of Eristatothanes

>>> r = range(2,200000)
>>> currentPrime = 2
>>> primes = []
>>> import math
>>> math.sqrt(200000)
447.21359549995793
>>> while currentPrime < 449:
... primes = primes + [currentPrime]
... r = filter(lambda n: (n % currentPrime) > 0, r)
... currentPrime = r[0]
...
>>> len(primes)
86
>>> len(r)
17898
>>> primes[85]
443
>>> r[0]
449
>>> 10001 - 86
9915
>>> r[9914]
104743
>>>

No comments: