Sieve of Atkin in Python 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 &lt; limit):
        y = 1
        while(y*y &lt; limit):
            n = (4*x*x)+(y*y)
            if n &lt;= limit and (n%12==5 or n%12==1):
                sieve_list[n] *= -1

            n = (3*x*x)+(y*y)
            if n &lt;= limit and n%12==7:
                sieve_list[n] *= -1

            n = (3*x*x)-(y*y)
            if n &lt;= limit and n%12==11 and x&gt;y:
                sieve_list[n] *= -1
            y += 1
        x += 1
    # Part II: Remove the squares of primes (and their multiples)
    r = 5
    while r*r &lt; limit:
        if sieve_list[r] &gt; 0:
            i = r*r
            while i &lt; 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 &gt; 0:
            results.append(x)
        x += 1
    return results
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 &lt; 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 &gt; 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 &gt; 3
    sieve_list = [False] * (limit + 1)
    sieve_list[2:4] = (True, True)

    # Part I: preliminary work
    x = x_squared = 1
    while x_squared &lt; limit:
        y = y_squared = 1
        while y_squared &lt; limit:
            n = 4 * x_squared + y_squared
            if n &lt;= limit and n % 12 in (1, 5):
                sieve_list[n] = not sieve_list[n]

            n = 3 * x_squared + y_squared
            if n &lt;= limit and n % 12 == 7:
                sieve_list[n] = not sieve_list[n]

            if x &gt; y:
                n = 3 * x_squared - y_squared
                if n &lt;= 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 &lt; 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]