Sieve of Atkin in Python

Question

I recently implemented the Sieve of Atkin prime generating algorithm in Python. Though I know the term "pythonic" isn't exactly set in stone, I can tell that my program doesn't quite take advantage of python's inherent traits; my program looks like it was written with "C" in mind.

My question is two fold; (1) how can I make this more pythonic, and (2) how can I improve its performance?

I suspect the solution lies in making less use of lists in lieu of generators, but I'm not sure how to do so here:

def atkin_sieve(limit):
 sieve_list = [-1]*limit
 sieve_list[2] *= -1
 sieve_list[3] *= -1
 x = 1
 # Part I: preliminary work
 while(x*x < limit):
 y = 1
 while(y*y < limit):
 n = (4*x*x)+(y*y)
 if n <= limit and (n%12==5 or n%12==1):
 sieve_list[n] *= -1
 n = (3*x*x)+(y*y)
 if n <= limit and n%12==7:
 sieve_list[n] *= -1
 n = (3*x*x)-(y*y)
 if n <= limit and n%12==11 and x>y:
 sieve_list[n] *= -1
 y += 1
 x += 1
 # Part II: Remove the squares of primes (and their multiples)
 r = 5
 while r*r < limit:
 if sieve_list[r] > 0:
 i = r*r
 while i < limit:
 sieve_list[i] = -1
 i += r*r
 r += 1
 # Part III: Append everything into a list
 results = []
 x = 0
 for p in sieve_list:
 if p > 0:
 results.append(x)
 x += 1
 return results

Answer 1

So I recast your code to make it a bit more pythonic. For reference, all of the code is at the bottom of this post. I played around a bit looking for some performance improvements, but found nothing significant.

Some notes:

Pep8:

First thing to do is get a style/lint checker. I use the pycharm ide which will show you style and compile issues right in the editor. When you get a chance you should also read through pep8 which is the official python style guide.

Native Types:

I changed all of the +/-1 to True/False

Bug at a boundary:

The sieve_list list was one element too short. I discovered this with a quick sanity test of:

print atkin_sieve(28)
print atkin_sieve(29)
print atkin_sieve(30)

Use python iterators:

This:

i = r*r
while i < limit:
 sieve_list[i] = -1
 i += r*r

became:

for n in range(r_squared, len(sieve_list), r_squared):
 sieve_list[n] = False

And this:

results = []
x = 0
for p in sieve_list:
 if p > 0:
 results.append(x)
 x += 1
return results

became:

return [x for x, p in enumerate(sieve_list) if p]

Code:

def atkin_sieve(limit):
 assert limit > 3
 sieve_list = [False] * (limit + 1)
 sieve_list[2:4] = (True, True)
 # Part I: preliminary work
 x = x_squared = 1
 while x_squared < limit:
 y = y_squared = 1
 while y_squared < limit:
 n = 4 * x_squared + y_squared
 if n <= limit and n % 12 in (1, 5):
 sieve_list[n] = not sieve_list[n]
 n = 3 * x_squared + y_squared
 if n <= limit and n % 12 == 7:
 sieve_list[n] = not sieve_list[n]
 if x > y:
 n = 3 * x_squared - y_squared
 if n <= limit and n % 12 == 11:
 sieve_list[n] = not sieve_list[n]
 y += 1
 y_squared = y * y
 x += 1
 x_squared = x * x
 # Part II: Remove the squares of primes (and their multiples)
 r = 5
 r_squared = r * r
 while r_squared < limit:
 if sieve_list[r]:
 for n in range(r_squared, len(sieve_list), r_squared):
 sieve_list[n] = False
 r += 1
 r_squared = r * r
 # Part III: Append everything into a list
 return [x for x, p in enumerate(sieve_list) if p]

• daOnlyBG: That's pretty nifty- thanks. Question, though: would I find a performance improvement in xrange instead of range in part II?
• Stephen Rauch: Yes, with python 2.
• daOnlyBG: One more question: you have sieve_list[n] = not sieve_list[n] in Part I, when the program tests the modulo cases. Curiously enough, I just left those as sieve_list[n] = False and I saw that the code did not work properly until I formatted as you did. Why does flipping the boolean case require the not keyword but does not require it below in Part II, where you have sieve_list[n] = False?
• Stephen Rauch: The first is the sieve, the second is just removing. en.wikipedia.org/wiki/Sieve_of_Atkin
• Stephen Rauch: The sieve works by toggling the value to and fro, so it will not work just setting it True