By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Sieve of Eratosthenes

Previously, we implemented the Sieve of Eratosthenes. However, our implementation demands an integer $m$ and can only generate primes less than $m$. While some approximation algorithms for determining the $n$th prime are available, we would like to produce an exact solution. Hence, we must implement a prime sieve that does not require an upper bound.



In [1]:

    
from itertools import count, islice
from collections import defaultdict



In [2]:

    
def _sieve_of_eratosthenes():
    factors = defaultdict(set)
    for n in count(2):
        if factors[n]:
            for m in factors.pop(n):
                factors[n+m].add(m)
        else:
            factors[n*n].add(n)
            yield n



In [3]:

    
list(islice(_sieve_of_eratosthenes(), 20))









    Out[3]:





[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]



In [4]:

    
get_prime = lambda n: next(islice(_sieve_of_eratosthenes(), n, n+1))



In [5]:

    
# The Project Euler problem
# uses the 1-based index.
get_prime(10001-1)









    Out[5]:





104743

This implementation scales quite well, and has good space and time complexity.



In [6]:

    
get_prime(10**6)









    Out[6]:





15485867