I am trying to calculate the nth prime using the Sieve of Eratosthenes. For large values of n though, it would speed up the process to generate some lower bound, and then only sieve the values above this lower bound until the nth prime was found. The lower bound that I am using here is lower_bound = n * (ln + log(ln, e))
, where ln = log(n, e)
. This provides a decent estimation for values of n >= 2. Then I would use the Sieve of Eratosthenes to sieve starting from this lower bound until the nth prime is found. I have implemented this fully using this code:
def find_nth_prime(n, lower=3):
primes = [2]
previous_primes = primepi(lower)
candidate = lower
while len(primes) < (n - previous_primes + 2):
is_prime = True
for prime in primes:
if candidate % 5 == 0:
is_prime = False
break
if prime > ceil(sqrt(candidate + 1)):
break
if candidate % prime == 0:
is_prime = False
break
if is_prime:
primes.append(candidate)
candidate += 2
return primes[-1]
The problem with this code is that it does not test primality using the primes below this lower bound. For example, if I tried to do find_nth_prime(10, 5)
it would output 23 (the 9th prime) because it thinks that 9 is prime because it does not test for divisibility by 3, because it is below the lower bound and thus not included in the numbers it tests divisibility with. I have tried calculating the primes up until the lower bound, and then using this as my primes list in find_nth_prime
, but this defeats the purpose of having a lower bound in the first place. I can't just add the primes before because my goal is to use this function for fairly large values of n, so adding them in manually every time would be impractical. I also don't really want to import a list of primes because that also defeats the purpose and I could just use that list to find the nth prime. I have done some reading on other questions similar to this, like this one, but the explanation given does not explain how to sieve from a lower bound, it just simply says to do it. The link given at the bottom of that answer also no longer works. Thanks for the help.