Why is my implementation of the Sieve of Atkin overlooking numbers close to the specified limit?
Posted
by Ross G
on Stack Overflow
See other posts from Stack Overflow
or by Ross G
Published on 2010-03-08T02:00:54Z
Indexed on
2010/03/08
3:02 UTC
Read the original article
Hit count: 577
My implementation 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.
© Stack Overflow or respective owner
