DEV Community

loading...

Discussion on: 10001st prime - Project Euler Soution

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 Author • Edited

It can save time and space complexity.

Forem Open with the Forem app