# 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¶

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]:

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]:

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

In [6]:

```
get_prime(10**6)
```

Out[6]:

## Comments

Comments powered by Disqus