## DEV Community

Deepak Raj

Posted on • Updated on

# 10001st prime - Project Euler Soution

### Problem Statement:

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 10 001st prime number?

You can find the original question here -> Project Euler

### 10001st prime - Project Euler Solution in Python

``````import itertools

def is_prime(n):
for i in range(2, n//2 + 1):
if n % i == 0:
return False
else:
continue
return True

p = 0
for x in itertools.count(1):
if is_prime(x):
if p == 10001:
print(x)
break
p += 1
``````

Share Your Solutions for 10001st prime

Checkout the optimized solution in the comment section.

Using the Python extensible prime generator: "Iterative sieve on unbounded count from 2" function `prime_sieve` as posted on Rosetta Code.

```from itertools import count, islice

def prime_sieve():
sieved = count(2)
prime = next(sieved)
yield prime
primes = [prime]
for x in sieved:
if any(x % prime == 0 for prime in primes):
continue
yield x
primes.append(x)

if __name__ == '__main__':
print("Show the 10,001st prime.\n   =",
next(islice(prime_sieve(), 10_000, 10_001)))```

Modified to test less primes:

```from itertools import count, islice, takewhile

def prime_sieve2():
sieved = count(2)
prime = next(sieved)
yield prime
primes = [prime]
for x in sieved:
possible_prime_divs = takewhile(lambda p: p <= x**0.5, primes)
if any(x % prime == 0 for prime in possible_prime_divs):
continue
yield x
primes.append(x)

if __name__ == '__main__':
print("Show the 10,001st prime.\n   =",
next(islice(prime_sieve2(), 10_000, 10_001)))
```

Jing Xue

Reuse the smaller primes we found and only try divisions by them instead of every number. Also technically we only need to try up to `sqrt(n)` which is usually less than `n//2 + 1`.

``````import math

def nth_prime(n: int) -> int:
primes = [2]
m = 3
while len(primes) < n:
j = 0
sqrt_m = math.sqrt(m)
is_prime = True
while primes[j] <= sqrt_m:
if m % primes[j] == 0:
is_prime = False
break
j += 1
if is_prime:
primes.append(m)
m += 1
return primes[-1]

print(nth_prime(10001))
``````

Deepak Raj • Edited

It can save time and space complexity.

Galuh Utama

That‘s a quite slow algorithm. I suggest to look at sieve of atkin.

Deepak Raj

Thanks for suggesting.

Muhimen

Trying upto 10001 is not a good idea. And if the constraints go up you might even face TLE. Why don't use sieve?