2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – wolf-revo-cats Mar 9 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.