My implementation of Sieve of Atkin either overlooks primes near the limit or composites near the limit. while some limits work and others don't. I'm am completely confused as to what is wrong.
def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
for j in range(1, factor):
n = 4*i**2+j**2
if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
sieve[n] = not sieve[n]
n = 3*i**2+j**2
if (n <= lim) and (n % 12 == 7):
sieve[n] = not sieve[n]
if i>j:
n = 3*i**2-j**2
if (n <= lim) and (n % 12 == 11):
sieve[n] = not sieve[n]
for index in range(5,factor):
if sieve[index]:
for jndex in range(index**2, limit, index**2):
sieve[jndex] = False
for index in range(7,limit):
if sieve[index]:
results.append(index)
return results
For example, when I generate a primes to the limit of 1000, the Atkin sieve misses the prime 997, but includes the composite 965. But if I generate up the limit of 5000, the list it returns is completely correct.
lim
tolimit
. Of course you must have known that.sieve = [False]*limit
, the largest index allowed islimit-1
.However, on this line
you are checking if
n<=limit
. Ifn==limit
thensieve[n]
raises an IndexError. Try your algorithm with a small value oflimit
(e.g. n=50). You'll see this error come up. An easy fix is to useThe easy fix is a bit wasteful since sieve[0] is never used. So you might think a better fix is to keep
sieve = [False]*limit
, but fix all your other code by stepping the index onsieve
down by one. (E.g., changesieve[n]
tosieve[n-1]
everywhere, etc.) However, this will force you to do a number of extra subtractions which will not be good for speed. So the easy/wasteful solution is actually probably the better option.In your code
and
int
takes the floor ofmath.sqrt(limit)
. Furthermore,range(1,factor)
goes from 1 to factor-1. So you are off by 1.So you need to change this to