I take it back... Tim's (really Will Ness's) version is *always* faster and more memory friendly. I'm still trying to understand it though :-).
On Thu, Jul 12, 2018 at 6:05 PM David Mertz <me...@gnosis.cx> wrote: > > On Thu, Jul 12, 2018 at 2:22 PM Chris Angelico <ros...@gmail.com> wrote: > >> On Fri, Jul 13, 2018 at 4:11 AM, Steven D'Aprano <st...@pearwood.info> >> wrote: >> > There is no reason why primality testing can't be deterministic up to >> > 2**64, and probabilistic with a ludicrously small chance of false >> > positives beyond that. The implementation I use can be expected to fail >> > on average once every 18 thousand years if you did nothing but test >> > primes every millisecond of the day, 24 hours a day. That's good enough >> > for most purposes :-) >> >> What about false negatives? Guaranteed none? The failure mode of the >> function should, IMO, be a defined and documented aspect of it. >> > > Miller-Rabin or other pseudo-primality tests do not produce false > negatives IIUC. > > 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). > > 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 > > > So then how do you implement isprime(). One naive way is to compare it > against elements of sieve_generator() until we are equal or larger than the > test element. But that's not super fast. A pseudo-primality test is much > faster (except for in the first few hundred thousand primes, maybe). > > -- > 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. > -- 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/
