Oops... yeah. I had fixed the "up to and including" previously, but somehow I copied the wrong version to the thread. On Thu, Jul 12, 2018 at 6:36 PM Tim Peters <tim.peters@gmail.com> wrote:
[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`.
-- Keeping medicines from the bloodstreams of the sick; food from the bellies of the hungry; books from the hands of the uneducated; technology from the underdeveloped; and putting advocates of freedom in prisons. Intellectual property is to the 21st century what the slave trade was to the 16th.