Generators/iterators, Pythonicity, and primes

[Miles]

On Sat, Apr 4, 2009 at 2:50 PM, John Posner wrote:
> Inspired by recent threads (and recalling my first message to Python
> edu-sig), I did some Internet searching on producing prime numbers using
> Python generators. Most algorithms I found don't go for the infinite,
> contenting themselves with "list all the primes below a given number".
>
> Here's a very Pythonic (IMHO) implementation that keeps going and going and
> going ...:
>
> from itertools import count
> from math import sqrt
>
> def prime_gen():
>     """
>     Generate all prime numbers
>     """
>     primes = []
>     for n in count(2):
>         if all(n%p for p in primes if p < sqrt(n)):
>             primes.append(n)
>             yield n
>
> The use of all() is particularly nifty (see
> http://code.activestate.com/recipes/576640/). And so is the way in which the
> list comprehension easily incorporates the sqrt(n) optimization.
>
> Question: Is there a way to implement this algorithm using generator
> expressions only -- no "yield" statements allowed?

def prime_gen():
    primes = []
    return (primes.append(n) or n for n in count(2) if all(n%p for p
in primes if p<=sqrt(n)))

That version is only marginally faster than your original version.
The biggest performance penalty is that the (... for p in primes ...)
generator isn't aborted once p > sqrt(n). Here's a less nifty but much
more efficient version:

def prime_gen():
    prime_list = [2]
    for p in prime_list: yield p
    for n in itertools.count(prime_list[-1] + 1):
        for p in prime_list:
            if p * p > n:
                prime_list.append(n)
                yield n
                break
            elif n % p == 0:
                break
        else:
            raise Exception("Shouldn't have run out of primes!")

When generating the first 1000 primes, this version's approximately 20
times faster; for the first 10,000 primes, ~80x (but still much slower
than a simple Sieve of Eratosthenes).  To make repeated calls faster,
move prime_list = [2] outside the function.

-Miles

P.S. Gmail shows all your messages with a blank body and a text
attachment containing your message; this is perhaps because your
mailer includes an invalid blank Content-disposition header.