Short Eratosthenes Sieve I've written a short implementation of the Eratosthenes' sieve.

def sieve(n):
    l = list(range(2, n + 1))
    out = []
    while len(l) &gt; 0:
        out.append(l[0])
        l = list(filter(lambda n: n % l[0], l))
    return out


Is it lacking in efficiency? Are there any improvements or changes you would make?
Yes, the implementation is short.  However, its efficiency is suspect.  That's due to:


Reassembling list every iteration
Testing every remaining member of list using % operator


The beauty of Eratosthenes' sieve is that it shouldn't need any division (including %).  With an array of values, we simply march along it in steps of n striking out members - that requires only addition, which is one of the cheapest operations in a digital computer.  (There's an optimisation that also requires multiplying a number by itself; that's only used because it's faster than the equivalent additions).

Removing the empty cells at every iteration prevents us from accessing every nth element in this way, as well as imposing its own overheads (for a start, we'll need lots of extra memory when building the new list from the old).