Generators/iterators, Pythonicity, and primes

[John Posner]

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