Get nth prime number using sieve of Eratosthenes

Question

I am tasked with being able to find the \$n\$th prime number. I've tried to implement something like the sieve of Eratosthenes in increments of 200. The code works and returns the \$n\$th prime number. However, when asking for the 1000th prime number I already notice a significant lag on my box.

This code needs to be able to quickly return the \$n\$th prime where \$n\$ is a massive number. For the challenge I only need to get up to 200,000. However, being able to finalize this for efficient use for up to a million would be pretty awesome, I think.

This is what I have working so far:

def nthPrime(ind): #gets nth prime number. IE: 5th prime == 11. works based off very in-efficient version of Sieve of Eratosthenes. but in increments of 200
    p={}
    T = 2
    incST = 2
    incEND = incST + 200
    lenfinal = 1

    while lenfinal <= ind:
        for i in range(incST,incEND):
            p[i] = True
        T=2
        while T <= math.sqrt(incEND):
            l = 0
            while l <= incEND:
                if T**2 + (T*l) >= incST:
                    p[T**2 + (T*l)] = False
                l+=1
                if T**2+(T*l) > incEND:
                   break

            for k,v in sorted(p.items()):
                if v and k > T:
                    T = int(k)
                    break


        incST = incEND + 1
        incEND = incST + 200
        lenfinal = sum(1 for k,v in p.items() if v)


    final = [k for k,v in sorted(p.items()) if v]
    return final[ind-1]

Answer 1

First a small stylistic review, followed by an alternative algorithm.

You calculate math.sqrt(incEND) many times, just calculate it once outside of the inner while loop. Similarly, you calculate T**2 + (T*l) two to three times per loop. Do it once and save it to a variable.

Python has an official style-guide, PEP8, which recommends using a space in a comma-separated argument list, so use range(incST, incEND) and for k, v in ...

It also recommends using lower_case_with_underscores for variables and function names and using a space before and after the = in variable assignments.

You did not include the import math, which you should do for completeness.

---

It is probably more efficient to take a prime number generator and count up to the nth prime than keeping a list of all prime numbers in memory.

For this I would use something like this, which I got from a python cookbook site. Alternative algorithms can be found, for example in this Stack Overflow post. It is basically also a Sieve of Eratosthenes, but one where the yielding and the marking-off are interleaved.

def primes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {}
    yield 2
    # start counting at 3 and increment by 2
    for q in itertools.count(3, 2):
        p = D.pop(q, None)
        if p is None:
            # q not a key in D, so q is prime, therefore, yield it
            yield q
            # mark q squared as not-prime (with q as first-found prime factor)
            D[q*q] = q
        else:
            # let x <- smallest (N*p)+q which wasn't yet known to be composite
            # we just learned x is composite, with p first-found prime factor,
            # since p is the first-found prime factor of q -- find and mark it
            x = p + q
            while x in D or x % 2 == 0:
                x += p
            D[x] = p

And then finding the nth prime becomes trivial:

def nth_prime(n):
    if n < 1:
        raise ValueError("n must be >= 1 for nth_prime")
    for i, p in enumerate(primes(), 1):
        if i == n:
            return p

This takes about 1 second to find the 200,000th prime (2750159) on my machine.

Answer 2

Graipher gave a good review. I'm just giving a slightly different take on the alternate.

You write "where n is a massive number" but I infer you mean "about 1 million" for massive, which seems very small. Using much more complicated methods, we can get the nth prime for 2e12 in under 1 second. But let's ignore that and just go with a goal of 1 to 10 million and a time frame of a second or two, which is a much simpler problem.

Given the smaller problem, we can break this into some steps that are very common.

1. Given n, find pn_upper where the nth prime pn <= pn_upper.
2. Sieve primes to pn_upper
3. Return the nth entry.

There are lots of upper bounds to be found, and if we wanted to go very high we might want to look into better ones (e.g. Dusart 2010 or Axler 2013). We can go with a basic one from Rosser and Schoenfeld 1962 with a simple one for inputs under 20.

For sieving, we can use Robert William Hanks' short Python monolithic sieve from Fastest way to list all primes below N. We could be even faster with the numpy version or going to a complicated segmented sieve, but this is pretty good and short. It's not the most obvious, but we can think of it as a library function.

from math import ceil, log

def rwh_primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n/3)
    for i in xrange(1,int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k/3      ::2*k] = [False]*((n/6-k*k/6-1)/k+1)
        sieve[k*(k-2*(i&1)+4)/3::2*k] = [False]*((n/6-k*(k-2*(i&1)+4)/6-1)/k+1) 
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def nth_prime(n):
    if n < 1:
      raise ValueError("n must be >= 1 for nth_prime")
    ln  = log(n)
    pn_upper = int(n*(ln+2)) if n <= 20 else int(ceil(n * (ln + log(ln) - 0.5)))
    return rwh_primes(pn_upper)[n-1]

About 0.05 seconds for n=200,000. 0.3 seconds for n=1,000,000. 3.2 seconds for n=10,000,000. Using the numpy version of his sieve drops the latter to 0.6 seconds.