Python: Trouble testing primality of a number using Sieve of Eratosthenes

36 views Asked by At

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.

0

There are 0 answers