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]