Simple Sieve of Eratosthenes in Python 3

So yet another Sieve of Eratosthenes in Python 3.

The function returns a list of all primes smaller but not equal max_n.

The motivation is, as a practice, a simple implementation of the algorithm that is faithful, short, readable and transparent, while still getting a reasonable performance.

def primes(max_n):
"""Return a list of primes smaller than max_n."""

sieve = [True] * max_n

# p contains the largest prime yet found.
p = 2

# Only for p < sqrt(max_n) we check,
# i.e. p ** 2 < max_n, to avoid float issues.
while p ** 2 < max_n:

# Cross-out all true multiples of p:
for z in range(2 * p, max_n, p):
sieve[z] = False

# Find the next prime:
for z in range(p + 1, max_n):
if sieve[z]:
p = z
break

# 0 and 1 are not returned:
return [z for z in range(2, max_n) if sieve[z]]

IMHO it would be preferable to avoid p ** 2 < max_n and instead use p < max_n ** 0.5. Can we do this? It surprisingly seems to work as long as max_n ** 0.5 fits into the float mantissa, even if max_n doesn’t.

The second for-loop doesn’t look very nice with the break but I don’t have any idea how to do it otherwise…

Do you have any suggestions?

Are there still any simplifications possible? Or non-hackish ways to increase performance?

The second for-loop doesn’t look very nice with the break ...

You can remove that for-loop if you test p for being prime in the while-loop:

while p ** 2 < max_n:
if sieve[p]:
# p is prime: cross-out all true multiples of p:
for z in range(2 * p, max_n, p):
sieve[z] = False
p += 1

Are there still any simplifications possible? Or non-hackish ways to increase performance?

Here are two simple changes which increase the performance: First, since 2 is the only even prime, you can increment p by two after the first iteration:

p = p + 2 if p > 2 else 3

Second, it suffices to “cross-out” the multiples of p starting at p*p (instead of 2*p) because all lesser multiples have been handled before:

for z in range(p * p, max_n, p):
sieve[z] = False
• It suffices to “cross-out” the multiples of p starting at p*p how could I not see this!!! ;-) . Now it’s 8 lines of actual code. – wolf-revo-cats Mar 9 at 7:28