# Generators/iterators, Pythonicity, and primes

John Posner jjposner at snet.net
Sun Apr 5 17:14:09 CEST 2009

```Kay Schluehr said:

> g = (lambda primes = []:
>       (n for n in count(2) \
>          if
>              (lambda n, primes: (n in primes if primes and
n<=primes[-1] \
>          else
>              (primes.append(n) or True \
>                  if all(n%p for p in primes if p <= sqrt(n)) \
>                  else False)))(n, primes)))()

Um ... did you say "easy"? :-) This is prodigious, and it's definitely a
solution to the generator-expression-only challenge I laid down. But I
think this is a case in which using a generator expression causes a loss
in "Pythonicity", rather than a gain. Many, many thanks for this!

Steven D'Aprano said:

> In other words, this is a crappy way to generate primes. It's a trick,
> not a good algorithm: slow and inefficient, as well as obfuscated.

I wasn't thinking at all about efficiency, so I'm not surprised that my
implementation -- a pretty simple adaptation of
http://code.activestate.com/recipes/576640 -- scores low in that
dimension. I was mainly looking for Pythonicity. I'm sure this means
different things to different people, PEP 20 notwithstanding. To me,
this is an important aspect of Pythonicity:

The final Python code looks like your initial back-of-the-napkin pseudo
code.

In the old days, that meant using filter(), because this function
mirrors the "sieve" concept in the Sieve of Eratosthenes. These days, I
believe that this condition:

if all(n%p for p in primes if p < sqrt(n)):

... closely resembles this pseudo code:

if the number cannot be evenly divided by all the primes we've
generated so far (and we can stop testing at the square root)

So I believe this algorithm is the *opposite* of obfuscated. It's
crystal clear (albeit a slowpoke).

Miles (and others) said:

> 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.

It might be my ISP (AT&T Yahoo), or it might be MS-Outlook. I'm sending
this message using Thunderbird 2.0.0.21. Any better?

-John

```