[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:

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, ceil

def up_to(seq, lim):

    for n in seq:

        if n < lim:

            yield n

        else:

            break

def sieve_generator():

    "Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"

    yield 2

    candidate = 3

    found = []

    while True:

        lim = int(ceil(sqrt(candidate)))

        if all(candidate % prime != 0 for prime in up_to(found, lim)):

            yield candidate

            found.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`.