genexp surprise (wart?)

Paul Rubin http
Fri May 26 07:53:36 CEST 2006

Paul Rubin <> writes:
> Yeah, it's just counterintuitive is all.  I guess the natural way to
> express this would have been with tail recursion instead of a while
> loop.

FWIW, here's a listcomp version:

    def s2(n=100):
        stream = range(2,n)
        while stream:
            p = stream[0]
            yield p
            stream = [s for s in stream if s%p != 0]

    print list(s2(100))

This should have the same space consumption and approx. running time
as the classic sieve.  The genexp version actually used O(n/log(n))
space instead of linear space, I think.

More information about the Python-list mailing list