Generators/iterators, Pythonicity, and primes

[John Posner]

Inspired by recent threads (and recalling my first message to Python
edu-sig), I did some Internet searching on producing prime numbers using
Python generators. Most algorithms I found don't go for the infinite,
contenting themselves with "list all the primes below a given number".

Here's a very Pythonic (IMHO) implementation that keeps going and going and
going ...:

from itertools import count
from math import sqrt

def prime_gen():
"""
Generate all prime numbers
"""
primes = []
for n in count(2):
if all(n%p for p in primes if p < sqrt(n)):
primes.append(n)
yield n

The use of all() is particularly nifty (see
http://code.activestate.com/recipes/576640/). And so is the way in which the
list comprehension easily incorporates the sqrt(n) optimization.

Question: Is there a way to implement this algorithm using generator
expressions only -- no "yield" statements allowed?

BTW -- thank you, John Machin, for the spanking ('I'd worry about "correct"
before "Pythonic"') in a previous message. I *did* manage to post a
correction to the needless conversion of a string to a list:

b in list("\r\n\t")

.... a few hours before your message arrived (Wed Apr 1 19:44:01 CEST 2009)!





E-mail message checked by Spyware Doctor (6.0.0.386)
Database version: 5.12110
http://www.pctools.com/en/spyware-doctor-antivirus/

 

[Kay Schluehr]

Question: Is there a way to implement this algorithm using generator

expressions only -- no "yield" statements allowed?

Yes. Avoiding the yield statement is easy but one might eventually end
up with two statements because one has to produce a side effect on the
primes list. However we can use default parameters in lambdas and
finally get a single expression which is a generator expression:

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

assert g.next() == 2
assert g.next() == 3
assert g.next() == 5
assert g.next() == 7

 

[Arnaud Delobelle]

Inspired by recent threads (and recalling my first message to Python
edu-sig), I did some Internet searching on producing prime numbers using
Python generators. Most algorithms I found don't go for the infinite,
contenting themselves with "list all the primes below a given number".

Here's a very Pythonic (IMHO) implementation that keeps going and
going and going ...:

from itertools import count
from math import sqrt

def prime_gen():
"""
Generate all prime numbers
"""
primes = []
for n in count(2):
if all(n%p for p in primes if p < sqrt(n)):
primes.append(n)
yield n

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

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

Of course there is no excuse for writing Python like that

 

[John Posner]

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

 

[Arnaud Delobelle]

I haven't timed it, but I would guess that the takewhile was faster
only because the sqrt(n) had been factored out of the loop. Try the
original loop again precalculating the sqrt(n) and see how that compares.

Most likely

 

[John Posner]

I haven't timed it, but I would guess that the takewhile was faster
only because the sqrt(n) had been factored out of the loop. Try the
original loop again precalculating the sqrt(n) and see how that compares.

Here's my "timeit" scorecard, with repeat=5 (only the minimum value
reported) and number=5000:

**** all prev. primes
3.97347791658

**** prev. primes that don't exceed SQRT
6.23250413579

**** [CACHED] prev. primes that don't exceed SQRT
3.45557325672

**** [TAKEWHILE] prev. primes that don't exceed SQRT
0.371197373201

**** [TAKEWHILE] squares, using *, of prev. primes that don't exceed N
0.358001074011

**** [TAKEWHILE] squares, using **, of prev. primes that don't exceed N
0.383540147515

**** [TAKEWHILE, CACHED] squares, using *, of prev. primes that don't
exceed N
0.410309506343

**** [TAKEWHILE, CACHED] squares, using **, of prev. primes that don't
exceed N
0.401269222462


So ... adding the SQRT optimization degrades the performance
significantly, but adding CACHING to the SQRT optimization swings the
performance pendulum back to the "benefit" side. TAKEWHILE is a big win,
but adding CACHING to TAKEWHILE degrades performance.

The code (110 lines) is at http://cl1p.net/python_prime_generators/

-John

 

[Arnaud Delobelle]

Which of course is rubbish, extracting the sdqrt will have an effect but
the main factor is that takewhile exits the loop as soon as the condition
is false whereas a conditional in a generator comprehension doesn't stop
the loop continuing to the end.

Absolutely! Since you hadn't quoted the original code, I'd forgotten
that it wasn't stopping after n**0.5.

 

[Aaron Brady]

Absolutely!  Since you hadn't quoted the original code, I'd forgotten
that it wasn't stopping after n**0.5.

-1 entertaining, list. Come on, people, the show must go on. Take
five.