Generators/iterators, Pythonicity, and primes

Arnaud Delobelle arnodel at
Sat Apr 11 23:26:05 CEST 2009

John Posner <jjposner at> 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),

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),

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


More information about the Python-list mailing list