Question

Can you describe some different algorithms for testing for primality?

Answer 1

The following program implements two different ways of testing for primality.

Answer 2

Here is the same program that evaluates the time it takes for each function to test the same number for primality:


from time import *
from math import *


def prime_test1(test_num):
for divisor in range (2,test_num):
if (test_num%divisor==0):
return (False)
return(True)

def prime_test2(test_num):
for divisor in range (2,int(sqrt(test_num))+1):
if (test_num%divisor==0):
return (False)
return(True)




myNum=int(raw_input('What number do you want to test? '))


start2 = clock()
print myNum, prime_test2(myNum)
end2 = clock()
time_elapsed2 = end2-start2
print "It took me - prime test #2: ", time_elapsed2


start1 = clock()
print myNum, prime_test1(myNum)
end1 = clock()
time_elapsed1 = end1-start1
print "It took me - prime test #1: ", time_elapsed1

Answer 3

One of the algorithms determined primality of the 7th million prime in milliseconds, whereas the other algorithm take about 18 seconds.

What number do you want to test? 122949823
122949823 True
It took me - prime test #2: 0.003406
122949823 True
It took me - prime test #1: 18.09801

The difference between the two grows exponentially as the number increases. The first algorithm successfully evaluates primality of the fiftieeth million prime number (982451653) in .0066 seconds. I dare not try to evaluate the same using the second algorithm. It will probably take days.

What number do you want to test? 982451653
982451653 True
It took me - prime test #2: 0.006579

Answer 4

here is one
http://codepad.org/hH6xPMKE

Answer 5

try it on your 'puter

Answer 6

couple more
http://pastebin.com/PnaANUFF
http://pastebin.com/rF99YsZi

Answer 7

here is one solution

http://www.ideone.com/rbDfd

Answer 8

i like lines 5,6,7 that real tight loop in 5/6 then a test at 7 - simple and effective
about 1/2 second to find the 1/1000th prime on my computer
http://pastebin.com/68c3zGGG