Get nth prime number using sieve of Eratosthenes 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 &lt;= ind:
        for i in range(incST,incEND):
            p[i] = True
        T=2
        while T &lt;= math.sqrt(incEND):
            l = 0
            while l &lt;= incEND:
                if T**2 + (T*l) &gt;= incST:
                    p[T**2 + (T*l)] = False
                l+=1
                if T**2+(T*l) &gt; incEND:
                   break

            for k,v in sorted(p.items()):
                if v and k &gt; 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]
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 &lt;- 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 &lt; 1:
        raise ValueError("n must be &gt;= 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.