On Wed, Aug 22, 2012 at 11:39:46PM -0400, Dave Angel wrote: > On 08/22/2012 07:32 PM, Richard D. Moores wrote: > > <snip> > > > > My code uses gmpy2.is_prime() (lines 79 and 89). is_prime() is VERY fast. > > You do know that this gmpy2 function is only statistically correct ? it > can false positive. I don't know what the probs are, but it uses > Miller-Rabin, with a default factor of 25.
What Dave means is: - If gmpy2.is_prime says a number is not prime, then that is certainly true; - but if it says that a number is prime, then that is only probably true. With 25 Miller-Rabin tests, the probability of a false positive is (if I remember correctly) 1 time in 4**25 or about 1 time in a million billion. (That's American billion, 10**9, not old-style English billion.) If you tested a thousand prime numbers a second for thirty thousand years, you would expect perhaps one false positive. The odds are much higher that a hardware fault or stray cosmic ray hitting the CPU or memory chip will cause the computer to calculate the wrong answer. For anyone interested, here is my pyprimes module: http://pypi.python.org/pypi/pyprimes/ which is written in pure Python (no reliance on gmpy2), so you can actually see how the algorithms work, although it is correspondingly much slower. Source code can be found here: http://code.google.com/p/pyprimes/source/browse/src/pyprimes.py It is *extensively* documented. The API is alpha-quality and subject to change. -- Steven _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor