 # 10001st prime - Project Euler Soution CodePerfectPlus Updated on ・1 min read

Problem Solving Series(For Interview) (9 Part Series) ### 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

Problem Solving Series(For Interview) (9 Part Series)

Posted on by:

### Discussion 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)))


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 = 
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))


It can save time and space complexity.

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

Thanks for suggesting.

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