# Project Euler Problem 7: 10001st prime

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 :
from itertools import count, islice
from collections import defaultdict

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

In :
list(islice(_sieve_of_eratosthenes(), 20))

Out:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
In :
get_prime = lambda n: next(islice(_sieve_of_eratosthenes(), n, n+1))

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

Out:
104743

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

In :
get_prime(10**6)

Out:
15485867