Generators/iterators, Pythonicity, and primes

Kay Schluehr kay.schluehr at gmx.net
Sun Apr 5 18:57:31 CEST 2009


On 5 Apr., 18:47, John Posner <jjpos... at snet.net> wrote:
> 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.

Yes, sure. I developed is_prime as a standalone function with the
primes list as a cache and just lambda-fied it.

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

This is of course much more accessible and doesn't even look weird.

Regards



More information about the Python-list mailing list