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 function calls).

More readable implementation

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?