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 &lt; sqrt(max_n) we check,
    # i.e. p ** 2 &lt; max_n, to avoid float issues.
    while p ** 2 &lt; 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 &lt; max_n and instead use p &lt; 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 &lt; 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 &gt; 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