Eratosthenes' and Sundaram's prime sieves in Python

Question

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 <= new_limit):
        while (i + j + 2 * i * j <= 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 > 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)

Answer 1

There are some curious inconsistencies between the Eratosthenes and Sundaram code.

    for i in range(2, limit):
        if i * i > limit:
            break

is IMO more Pythonic than

    i = 1
    j = i
    while (i + j + 2 * i * j <= 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 <= new_limit):
        j = i
        ...
        i += 1

Then simplify algebraically:

    i = 1
    while (2 * i * (i + 1) <= new_limit):
        j = i
        ...
        i += 1

And finally replace with range:

    for i in range(1, new_limit + 1):
        if 2 * i * (i + 1) > 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.

Answer 2

• sieve_of_eratosthenes has an inner while loop that increments i. This is not useful because it will not advance the outer for loop, and you end up looping over the same values multiple times.
• sieve_of_sundaram repeats the expression i + j + 2 * i * j. You could instead use for loops with an appropriate step size.

Answer 3

Theory

def sieve_of_eratosthenes(limit):
    boolean_list = [True] * limit;

• There's no need for ;.
• It might be easier to add one element to the list and use 1-based indexing.

---

    for i in range(2, limit):
        if i * i > limit:
            break

• There's no need for this check. It will be integrated into your range later. If i * i is larger than limit, range(i * i, limit + 1, i) is empty and nothing happens.

---

        while boolean_list[i - 1] == False:
            i += 1

• You also don't need this loop, you already have for i above.

---

        for j in range(i * i, limit + 1, i):
            boolean_list[j - 1] = False

• This looks fine. With 1-based indexing, it becomes boolean_list[j] = False

---

    primes = []
    for i in range(1, limit):
        if boolean_list[i] == True:
            primes.append(i + 1)

• You already iterated over the whole range earlier. You could append the primes directly in the above loop.

Code

Here's the refactored code. It's much shorter and 3 times faster than your original code for the primes below 1 million:

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    primes = []
    for i in range(2, limit + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return primes

It's even shorter if you return a generator:

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    for i in range(2, limit + 1):
        if is_prime[i]:
            yield i
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

Answer 4

I suggest you some performance improvements.

1. Sieve of Sundaram can be implemented using only addition.

2. Rewrite inner for loop as slice assignment.

3. Use list comprehension in last step.

4. For sieve you can use list of integers or bytearray.