10001st prime - Project Euler Soution

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

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

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

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