Prime sieve generator I wrote a simple prime sieve in Python. But it ended up looking... ugly. I included a few of the most basic optimizations. When posting this question SE suggested a bunch of questions on the same topic, which lead me to some improvements. But few were in generator form.

It's the optimizations' fault.
Unfortunately I can't continue an outer loop from an inner loop, like I can in JavaScript. I very much disagree with Guido here, as it makes the inner loop clunky.

from itertools import count

def sieve():
    primes = [2]
    for candidate in count(start=3, step=2):
        cont = False
        n = 0
        while primes[n]**2 &lt;= candidate:  # You only need to check up to the square root of a number.
            if candidate % primes[n] == 0:
                cont = True  # outer
                break
            n = n + 1
        if cont:
            cont = False
            continue
        yield primes[-1]
        primes.append(candidate)


Can we make this more concise without changing the basic logic?
For example this is extremely concise, but it doesn't have some of the optimizations my code does.

For fun, I wrote the same logic in Javascript. This looks cleaner due to being able to continue an outer loop. But the lack of negative indices is a step backwards.


  function* sieve() {
    let primes = [2]
    counter: for (let candidate = 3;; candidate+=2) {
        for (let n = 1; primes[n]**2 &lt;= candidate; n++)
            if (candidate % primes[n] == 0)
                continue counter
        yield primes[primes.length - 1]
        primes.push(candidate)
    }
}
We can move the while loop into another function.

def is_prime(candidate, primes):
    n = 0
    while primes[n]**2 &lt;= candidate:
        if candidate % primes[n] == 0:
            return False
        n += 1
    return True

def sieve():
    primes = [2]
    for candidate in count(start=3, step=2):
        if not is_prime(candidate, primes):
            continue
        yield primes[-1]
        primes.append(candidate)

We can use itertools.takewhile to expose the while loop as an iterable.

def is_prime(candidate, primes):
    for prime in itertools.takewhile(lambda p: p**2 &lt;= candidate, primes):
        if candidate % prime == 0:
            return False
    return True

We can use any to make is_prime easier to read.

If for any of the values, candidate % prime == 0, are true the result is true.
If none of them are then it is false.
Since we want it to be the other way around we can just use not.

def is_prime(candidate, primes):
    return not any(
        candidate % prime == 0
        for prime in itertools.takewhile(lambda p: p**2 &lt;= candidate, primes)
    )

We can move is_prime back into the first function.

def sieve():
    primes = [2]
    for candidate in count(start=3, step=2):
        if not not any(
            candidate % prime == 0
            for prime in itertools.takewhile(lambda p: p**2 &lt;= candidate, primes)
        ):
            continue
        yield primes[-1]
        primes.append(candidate)

We can swap the if to cancel the continue and a not.
We can swap the any and == 0, with not all.
We can cancel the double not.


def sieve():
    primes = [2]
    for candidate in count(start=3, step=2):
        if all(
            candidate % prime
            for prime in itertools.takewhile(lambda p: p**2 &lt;= candidate, primes)
        ):
            yield primes[-1]
            primes.append(candidate)


At the expense of readability you can get the following trade offs.


There is a chance that using int(candidate ** 0.5).__ge__ is faster than the lambda.