DEV Community

Cover image for 10001st prime - Project Euler Soution
Deepak Raj
Deepak Raj

Posted on • Edited on

10001st prime - Project Euler Soution

10001st prime - Project Euler Soution

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        
Enter fullscreen mode Exit fullscreen mode

Share Your Solutions for 10001st prime

Checkout the optimized solution in the comment section.

Top comments (7)

Collapse
 
paddy3118 profile image
Paddy3118

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)))
Collapse
 
paddy3118 profile image
Paddy3118

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)))
Collapse
 
jingxue profile image
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))
Collapse
 
codeperfectplus profile image
Deepak Raj • Edited

It can save time and space complexity.

Collapse
 
gwutama profile image
Galuh Utama

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

Collapse
 
codeperfectplus profile image
Deepak Raj

Thanks for suggesting.

Collapse
 
muhimen123 profile image
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?