# Python3 - Prime Sieve

I've implemented two prime sieves in python 3 to find all prime numbers up to an upper limit n - n exlusive. The first one is rather naive, while the second one only considers odd numbers to begin with (some clever index-arithmetic is necessary).

Naive implementation:

def naive_sieve(n):
if n < 3:
return []

sieve = [False, False, True] + [True, False] * (n // 2 - 1)

for prime in range(3, int(n**0.5) + 1, 2):
if sieve[prime]:
for multiple in range(prime*prime, len(sieve), 2*prime):
sieve[multiple] = False

return [number for number, is_prime in enumerate(sieve) if is_prime]


I actually implemented the more advanced sieve twice. One time giving every little step a sub-function with name (to get the understanding right) and the second time without all these definitions (to minimize the number of function calls).

def easy_odd_sieve(n):
if n < 3:
return []

def number_of_odd_nums_below(n):
return n // 2

def greatest_odd_number_below(n):
return ceil(n) // 2 * 2 - 1

def index_of_odd_number(n):
return (n - 1) // 2

def odd_number_from_index(i):
return (2*i + 1)

sieve = [0] + [1] * (number_of_odd_nums_below(n) - 1)

for j in range(1, index_of_odd_number(greatest_odd_number_below(n ** 0.5)) + 1):
if sieve[j]:
for i in range(index_of_odd_number(odd_number_from_index(j) ** 2), len(sieve), odd_number_from_index(j)):
sieve[i] = False

return [2] + [odd_number_from_index(index) for index, is_prime in enumerate(sieve) if is_prime]


Final implementation:

def odd_sieve(n):
if n < 3:
return []

sieve = [0] + [1] * (n //2 - 1)

for j in range(1, ceil(n ** 0.5) // 2):
if sieve[j]:
for i in range((2*j)*(j + 1), len(sieve), 2*j + 1):
sieve[i] = False

return [2] + [2*index + 1 for index, is_prime in enumerate(sieve) if is_prime]


My questions regarding this code are:

• How does my general python programming style look like?
• Correctness. Is the code correct or did I overlook something? (I've checked that all sieves return the same list for n in range(1, 1000))
• Naming. Are the variable names clear to the reader? What would you change?

Your style generally looks fine. Do run flake8 and make the edits suggested, mostly adjusting whitespace. Starting out with zero and one, then switching to False, is a bit odd.
    sieve = [False, False, True] + [True, False] * (n // 2 - 1)

The function name of number_of_odd_nums_below() appears to be off-by-one, as it's missing a comment explaining one may only pass in odd numbers. With such a restriction it seems that greatest_odd_number_below() would simply become n - 2.