Python Implementation of the Sieve of Atkin

Question

My code works to give most primes, however it still include 1 and misses some numbers: 23 and 47 (when calculating prime numbers under 100). For some reason it includes 91, any ideas why?? I have been using the Wikipedia instructions for the Sieve of Atkin.

My code is as follows:

limit = 100
results = [2, 3, 5] #prime numbers
sieve = [i for i in range(limit + 1)] #numbers to test
TF = [False] * (limit + 1) #marks number as prime or not
ModFour = [1, 13, 17, 29, 37, 41, 49, 53]
ModSix = [7, 19, 31, 43]
ModTwelve = [11, 23, 47, 59]

for x in range(limit + 1):
    for y in range(limit + 1):
        test = 4 * x**2 + y**2 
        if test % 60 in ModFour:
            try:
                TF[test] = True
            except IndexError:
                pass 
        test = 3 * x**2 + y**2
        if test % 60 in ModSix:
            try:
                TF[test] = True
            except IndexError:
                pass 
        if x > y:
            test = 3 * x**2 - y**2
            if test % 60 in ModTwelve:
                try:
                    TF[test] = True         
                except IndexError:
                    pass 

for n in range(2, limit + 1):
    if TF[n] == True:
        for x in range((n**2), (limit + 1), (n**2)):
            TF[x] = False


for p in range(limit + 1):
    if TF[p] == True:
        results.append(sieve[p])


for prime in results:
    print prime

Any suggestions on optimisation of the sieve are welcome. Thanks

Have you compared your code to this similar problem? Check where your logic deviates from his. — WGS
– WGS, Commented Jan 29, 2015 at 18:06
@TheLaughingMan : Mine is different when I do - if test % 60 in ModFour(etc) -. However I don't know why his works but mine doesn't. He is also using a optimised version because his ranges go to the square root of limit + 1. — Tom
– Tom, Commented Jan 29, 2015 at 18:11

Community · Accepted Answer · 2017-05-23 11:57:00Z

1

You are not flipping TF[test] - you are just setting those elements to True. Compare against the code at (this SO question):

test = 4 * x**2 + y**2    | n = 4*x**2 + y**2
if test % 60 in ModFour:  | if n<=limit and (n%12==1 or n%12==5):
  try:                    |  
    TF[test] = True       |   is_prime[n] = not is_prime[n]
  except IndexError:      | 
    pass                  |

To remove the 1 from results, just start at TF[5] when building the results list:

for p in range(5, limit + 1):
    if TF[p] == True:
        results.append(sieve[p])

edited May 23, 2017 at 11:57

CommunityBot

11 silver badge

answered Jan 30, 2015 at 0:52

ErikR

52.2k9 gold badges78 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tom Over a year ago

Thanks, this now works. Can you explain why my code didn't work originally?

Collectives™ on Stack Overflow

Python Implementation of the Sieve of Atkin

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related