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.pet...@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.
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
