Nth Prime

Editorial

Nth Prime asks for the n-th prime number (the 1st being 2), combining primality testing with counting.

Approach

Test candidates one by one — each by trial division up to its square root — until you've found n primes. For large n, sieving up to an estimated bound (around n ln n) is faster than testing individually.

count = 0; num = 1
while count < n:
    num += 1
    if is_prime(num):
        count += 1
return num

Complexity

Trial division: roughly O(n √p) for the n-th prime p; a sieve is faster at scale.