Generators/iterators, Pythonicity, and primes

John Posner jjposner at snet.net
Sun Apr 5 18:47:29 CEST 2009


Kay Schluehr wrote:

 > That's because it is *one* expression. The avoidance of named
 > functions makes it look obfuscated or prodigious. Once it is properly
 > dissected it doesn't look that amazing anymore.
 >
 > Start with:
 >
 > (n for n in count(2) if is_prime(n, primes))
 >
 > The is_prime function has following implementation:
 >
 > def is_prime(n, primes):
 >     if primes and n<=primes[-1]:
 >         return n in primes
 >     else:
 >         if all(n%p for p in primes if p <= sqrt(n)):
 >             primes.append(n)
 >             return True
 >         else:
 >             return False

Your explication is excellent, Kay! In the is_prime() function, can't we 
omit the first three lines (if ... else), because it will *always* be 
the case that "n" exceeds all the primes we've gathered so far. I've 
tested the code with these lines omitted -- both with the separate 
is_prime() function and with the generator-expression-only 
implementation. It seems to work fine. Ex:

---
from itertools import count
from math import sqrt

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

for i in range(500):
    print g.next(),
---

Note that we don't need any backslashes, either.




More information about the Python-list mailing list