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).
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?