Primality Test v2.0

After feedback from some friends of mine, and doing a little bit of background research, I am writing this update to my original post last week.  As it turns out, by checking all the numbers in the form 6k ± 1  instead of checking each number up to the input value, I have increased the speed by 7 times! determineIsPrime3 (line 48 below) is the fastest algorithm so far.  determineIsPrime2, a simple comparision against the , was twice as fast as the original algorithm.

For now, I am putting this one to bed.  It was a fun exercise, but I have got what I need from it.

<br />
'''<br />
Checks the specified value to determine if it is a prime number.<br />
If it is not prime the divisor will be returned instead.</p>
<p>@author: Eric Silva<br />
'''</p>
<p>import math, time</p>
<p>#Change this value to whatever value you want to test for prime.<br />
#testValue = 65027<br />
#testValue = 155188329701<br />
testValue = 99194853094755497<br />
#testValue = 10888869450418352160768000001<br />
print 'Testing %d...' % testValue</p>
<p>def determineIsPrime(testPrime):<br />
    if testPrime % 2 == 0:<br />
        return 'Divisible by 2'<br />
    if testPrime % 3 == 0:<br />
        return 'Divisible by 3'<br />
    testNum = 7<br />
    testLimit = testPrime<br />
    while testLimit >= testNum:<br />
        if testPrime % testNum == 0:<br />
           return 'Divisible by %d' % testNum<br />
        testLimit = testPrime/testNum</p>
<p>        testNum = testNum + 2</p>
<p>    return '%d is prime!' % testPrime</p>
<p>def determineIsPrime2(testPrime):<br />
    if testPrime % 2 == 0:<br />
        return 'Divisible by 2'<br />
    if testPrime % 3 == 0:<br />
        return 'Divisible by 3'<br />
    testNum = 5<br />
    sqrt = math.sqrt(testPrime)<br />
    while testNum <= sqrt:<br />
        if testPrime % testNum == 0:<br />
           return 'Divisible by %d' % testNum</p>
<p>        testNum = testNum + 2</p>
<p>    return '%d is prime!' % testPrime</p>
<p>def determineIsPrime3(testPrime):<br />
    if testPrime % 2 == 0:<br />
        return 'Divisible by 2'<br />
    if testPrime % 3 == 0:<br />
        return 'Divisible by 3'<br />
    testNum = 7<br />
    sqrt = math.sqrt(testPrime)<br />
    while ((6 * testNum) + 1 <= sqrt) or ((6 * testNum) - 1 <= sqrt):<br />
        if testPrime % testNum == 0:<br />
           return 'Divisible by %d' % testNum</p>
<p>        testNum = testNum + 2</p>
<p>    return '%d is prime!' % testPrime</p>
<p>startTime = time.time()<br />
result = determineIsPrime(testValue)<br />
endTime = time.time()</p>
<p>print result<br />
print '1. Calculation took %f s\n' % (endTime - startTime)</p>
<p>startTime = time.time()<br />
result = determineIsPrime2(testValue)<br />
endTime = time.time()</p>
<p>print result<br />
print '2. Calculation took %f s\n' % (endTime - startTime)</p>
<p>startTime = time.time()<br />
result = determineIsPrime3(testValue)<br />
endTime = time.time()</p>
<p>print result<br />
print '3. Calculation took %f s\n' % (endTime - startTime)</p>
<p>

Results:

<br />
Testing 99194853094755497...<br />
99194853094755497 is prime!<br />
1. Calculation took 202.609000 s</p>
<p>99194853094755497 is prime!<br />
2. Calculation took 114.813000 s</p>
<p>99194853094755497 is prime!<br />
3. Calculation took 28.781000 s<br />