[David Mertz]

Miller-Rabin or other pseudo-primality tests do not produce false negatives IIUC.

That's true if they're properly implemented ;-) If they say False, the input is certainly composite (but there isn't a clue as to what a factor may be); if the say True, the input is "probably" a prime.

I'm more concerned in the space/time tradeoff in the primes() generator. I like this implementation for teaching purposes, but I'm well aware that it grows in memory usage rather quickly (the one Tim Peters posted is probably a better balance; but it depends on how many of these you create and how long you run them).

As you noted later:

The original version of this came from an ActiveState recipe that many on c.l.py contributed to (including me) years ago, and that's where all the speed came from. There is, for example, no division or square roots. Will's contribution was the unexpected way to slash memory use, via the generator calling itself recursively. Elegant and effective!

Picture doing the Sieve of Eratosthenes by hand, crossing out multiples of "the next" prime you find. That's basically what it's doing, except doing the "crossing out" part incrementally, using a dict to remember, for each prime p, "the next" multiple of p you haven't yet gotten to.

I take it back... Tim's (really Will Ness's) version is *always* faster and more

memory friendly.

The original version of this came from an ActiveState recipe that many on c.l.py contributed to (including me) years ago, and that's where all the speed came from. There is, for example, no division or square roots. Will's contribution was the unexpected way to slash memory use, via the generator calling itself recursively. Elegant and effective!

I'm still trying to understand it though :-).

Picture doing the Sieve of Eratosthenes by hand, crossing out multiples of "the next" prime you find. That's basically what it's doing, except doing the "crossing out" part incrementally, using a dict to remember, for each prime p, "the next" multiple of p you haven't yet gotten to.

from math import sqrt, ceildef up_to(seq, lim):for n in seq:if n < lim:yield nelse:breakdef sieve_generator():"Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"yield 2candidate = 3found = []while True:lim = int(ceil(sqrt(candidate)))if all(candidate % prime != 0 for prime in up_to(found, lim)):yield candidatefound.append(candidate)candidate += 2

Note that this generates squares of odd primes too (9, 25, ...). `up_to` needs to be more like `up_to_and_including`.