Prime number testing

[Paul Miller]

codelykos at yahoo.com (Rahul) wrote in message news:<9d234d68.0407102202.47b5cb43 at posting.google.com>...
> HI.
> Python , with its support of arbit precision integers, can be great
> for number theory. So i tried writing a program for testing whether a
> number is prime or not. But then found my function painfully slow.Here
> is the function :
> 
> from math import sqrt
> def isPrime(x):
>     if x%2==0 or x%3==0:
>        return 0
>     i=5
>     sqrt=sqrt(x)
>     sqrt=sqrt(x)+1
>     while i<sqrt:
>        if x%i==0:
>           return 0
>        i=i+2
>        if x%i==0:
>           return 0
>        i=i+4
>     return 1
> 
> Try testing some number like 2**61-1.Its very slow.

Actually I find this function runs quite fast, although it terminates
with an UnboundLocalError. :P

What you probably meant was something like this:

import math

def isPrime (x):
	if x % 2 == 0: 
		return 0
	limit = int(math.sqrt (x))
	for i in xrange (3,limit+1,2):
		if x % i == 0:
			return 0
	return 1

I know your function attempted to sieve out multiples of 3 as well,
but that only improves performance in case x is composite.

Looking at this and assuming that 2**61 -1 is prime, you find that
this will do (2**61-1) or about 2**60 divisions.  If you assume you
can perform 10**9 divisions per sec, then this will take about 36
years. That's why your function is slow.

You could improve this a bit by dividing by only prime numbers. 
However, there are approximately 55997641048889848 +- 183279217216552
prime numbers <= 2**61-1, which means you'll now "only" be performing
about 2**55 divisions, a speedup of about 32 times, or approximately 1
year 2 months.  The catch is you need a lot of memory to store all
those primes. ;) [417214937 gigabytes, or so, provided you don't
introduce a compression scheme, which would slow you down a bit]

So, basically, trial division is hopeless for finding any but small
prime numbers.  (See http://www.utm.edu/research/primes/howmany.shtml
if you'd like to check my numbers.)

> In comparision
> Mathematica not only tests but finds factors in an instant by
> Divisors[x].

According to http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html,
Mathematica implements primality testing thusly:

"Mathematica versions 2.2 and later have implemented the multiple
Rabin-Miller test combined with a Lucas pseudoprime test as the
primality test used by the function PrimeQ[n]. As of 1997, this
procedure is known to be correct only for all , but no counterexamples
are known and if any exist, they are expected to occur with extremely
small probability (i.e., much less than the probability of a hardware
error on a computer performing the test)."

> Does anybody have a faster way to test for primality.(and not just
> pseudoprime).

Yes.  See above.