Topic: 10001st prime
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.
Top comments (7)
Using the Python extensible prime generator: "Iterative sieve on unbounded count from 2" function
prime_sieve
as posted on Rosetta Code.Modified to test less primes:
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 thann//2 + 1
.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?