Generators/iterators, Pythonicity, and primes

John Posner jjposner at snet.net
Sun Apr 12 03:21:18 CEST 2009


Arnaud Delobelle wrote:
> 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),
>           count(2)
> )
>
Formidable! (both the English and French meanings) This is the most 
elegant, Sieve of Eratosthenes-like solution.
> 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),
>     count(2)
> )
>   

Do know what in the itertools implementation causes adding a 'if p <= sqrt(n)'
clause to *decrease* performance, while adding a 'takewhile()' clause *increases* performance?

> Of course there is no excuse for writing Python like that :)
+1 (but it's fun every once in a while, eh?)

Thanks a lot!  -John





More information about the Python-list mailing list