Eratosthenes' and Sundaram's prime sieves in Python I recently started playing with Python. What can I do better?

def sieve_of_sundaram(limit):
    new_limit = (limit - 1) // 2
    boolean_list = [True] * new_limit;
    i = 1
    j = i
    while (i + j + 2 * i * j &lt;= new_limit):
        while (i + j + 2 * i * j &lt;= new_limit):
            boolean_list[2 * i * j + i + j - 1] = False
            j += 1
        i += 1
        j = i
    primes = [2]
    for i in range(0, new_limit):
        if boolean_list[i]:
            primes.append(i * 2 + 3)
    return primes

def sieve_of_eratosthenes(limit):
    boolean_list = [True] * limit;
    for i in range(2, limit):
        if i * i &gt; limit:
            break
        while boolean_list[i - 1] == False:
            i += 1
        for j in range(i * i, limit + 1, i):
            boolean_list[j - 1] = False
    primes = []
    for i in range(1, limit):
        if boolean_list[i] == True:
            primes.append(i + 1)
    return primes


i = 100
sundaram_primes = sieve_of_sundaram(i)
eratosthenes_primes = sieve_of_eratosthenes(i)

print("Sundaram primes count: ", len(sundaram_primes))
print(sundaram_primes)
print("Eratosthenes primes count: ", len(eratosthenes_primes))
print(eratosthenes_primes)
There are some curious inconsistencies between the Eratosthenes and Sundaram code.


    for i in range(2, limit):
        if i * i &gt; limit:
            break



is IMO more Pythonic than


    i = 1
    j = i
    while (i + j + 2 * i * j &lt;= new_limit):
        ...
        i += 1
        j = i



We can refactor the second into something similar to the first: firstly, observe that there's no need to repeat the assignment j = i:

    i = 1
    while (i + i + 2 * i * i &lt;= new_limit):
        j = i
        ...
        i += 1


Then simplify algebraically:

    i = 1
    while (2 * i * (i + 1) &lt;= new_limit):
        j = i
        ...
        i += 1


And finally replace with range:

    for i in range(1, new_limit + 1):
        if 2 * i * (i + 1) &gt; new_limit:
            break
        j = i
        ...


As noted by Janne, you can then refactor the inner loop to also use range...



The indexing of the arrays in both is a bit tricky. Are the maintenance costs worth saving four bytes of memory? If so, would it at least be worth leaving a comment to explain why (for example) the primes recovered by the Sundaram sieve are 2 * i + 3 instead of the 2 * i + 1 which someone who just read the Wikipedia page would expect?




    primes = [2]
    for i in range(0, new_limit):
        if boolean_list[i]:
            primes.append(i * 2 + 3)



can be written as a one-liner using something called list comprehensions. This is something that's worth learning because it's very common style for Python.

    primes = [2] + [i * 2 + 3 for i in range(0, new_limit) if boolean_list[i]]





        if boolean_list[i]:



...


        if boolean_list[i] == True:



What's the difference?

Answer: the first one is better style. x == True should be rewritten as x ; and y == False or y != True should be rewritten as not y. With good variable names this usually gives a very natural reading.



On the subject of names: boolean_list tells me the type, but what I care about is the meaning. For Eratosthenes that's easy: a True means that the index is a prime, and a False means that it's a composite number, so is_prime is a good name. For Sundaram the exact interpretation is a bit trickier, but is_prime would still work.