Generators/iterators, Pythonicity, and primes

[Arnaud Delobelle]

John Posner <jjposner at snet.net> writes:

> 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

You could do something like this with the help of itertools.ifilter:

prime_gen = ifilter(
          lambda n, P=[]: all(n%p for p in P) and not P.append(n),
          count(2)
)

I omitted the 'if p <= sqrt(n)' as it doesn't help the generator go
faster. You could use itertools.takewhile for that:

prime_gen = ifilter(
    lambda n, P=[]:
        all(n%p for p in takewhile(lambda p, s=n**0.5: p<=s, P))
        and not P.append(n),
    count(2)
)

Of course there is no excuse for writing Python like that :)

-- 
Arnaud