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?
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.
from itertools import count, islice from collections import defaultdict
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
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
get_prime = lambda n: next(islice(_sieve_of_eratosthenes(), n, n+1))
# The Project Euler problem # uses the 1-based index. get_prime(10001-1)
This implementation scales quite well, and has good space and time complexity.