Prime number testing
Rahul
codelykos at yahoo.com
Sun Jul 11 02:02:21 EDT 2004
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.In comparision
Mathematica not only tests but finds factors in an instant by
Divisors[x].
Does anybody have a faster way to test for primality.(and not just
pseudoprime).
rahul
More information about the Python-list
mailing list