Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!news.glorb.com!news-out.octanews.net!indigo.octanews.net!auth.beige.octanews.com.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.python
Subject: Re: How can I speed up a script that iterates over a large range (600 billion)?
References: <f97b3159-318a-41e2-9f28-339fa4a81d79@k6g2000yqc.googlegroups.com> <its0ar02sia@news2.newsguy.com>
Date: Tue, 21 Jun 2011 23:23:12 -0700
Message-ID: <7xiprybd0v.fsf@ruckus.brouhaha.com>
Organization: Nightsong/Fort GNOX
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux)
Cancel-Lock: sha1:tB9W6cHSYWCAoj/NZyK04c5G44s=
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Lines: 21
NNTP-Posting-Date: 22 Jun 2011 01:23:12 CDT
X-Complaints-To: abuse@octanews.net
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8188

Chris Torek <nospam@torek.net> writes:
> def primes():
>     """
>     Yields sequence of prime numbers via Sieve of Eratosthenes.
>     """

I think this has the same order-complexity but is enormously slower in
practice, and runs out of recursion stack after a while.  Exercise: spot
the recursion.

    from itertools import islice, ifilter, count

    def primes():
        a = count(2)
        while True:
            p = a.next()
            yield p
            a = ifilter(lambda t,p=p: t%p, a)

    # print first 100 primes
    print list(islice(primes(), 100))