«

»

Dec 14 2009

Print this Post

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 \scriptstyle{}\leq\sqrt n 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 \scriptstyle\sqrt n, 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.


'''
Checks the specified value to determine if it is a prime number.
If it is not prime the divisor will be returned instead.
@author: Eric Silva
'''
import math, time

#Change this value to whatever value you want to test for prime.
#testValue = 65027
#testValue = 155188329701
testValue = 99194853094755497
#testValue = 10888869450418352160768000001
print 'Testing %d...' % testValue

def determineIsPrime(testPrime):
    if testPrime % 2 == 0:
        return 'Divisible by 2'
    if testPrime % 3 == 0:
        return 'Divisible by 3'

    testNum = 7
    testLimit = testPrime

    while testLimit >= testNum:
        if testPrime % testNum == 0:
           return 'Divisible by %d' % testNum
        testLimit = testPrime/testNum

        testNum = testNum + 2
    return '%d is prime!' % testPrime

def determineIsPrime2(testPrime):
    if testPrime % 2 == 0:
        return 'Divisible by 2'
    if testPrime % 3 == 0:
        return 'Divisible by 3'

    testNum = 5
    sqrt = math.sqrt(testPrime)

    while testNum
        if testPrime % testNum == 0:
           return 'Divisible by %d' % testNum
        testNum = testNum + 2
    return '%d is prime!' % testPrime

def determineIsPrime3(testPrime):
    if testPrime % 2 == 0:
        return 'Divisible by 2'
    if testPrime % 3 == 0:
        return 'Divisible by 3'

    testNum = 7
    sqrt = math.sqrt(testPrime)

    while ((6 * testNum) + 1
        if testPrime % testNum == 0:
           return 'Divisible by %d' % testNum
        testNum = testNum + 2
    return '%d is prime!' % testPrime

startTime = time.time()

result = determineIsPrime(testValue)

endTime = time.time()

print result

print '1. Calculation took %f s\n' % (endTime - startTime)

startTime = time.time()

result = determineIsPrime2(testValue)

endTime = time.time()

print result

print '2. Calculation took %f s\n' % (endTime - startTime)

startTime = time.time()

result = determineIsPrime3(testValue)

endTime = time.time()

print result

print '3. Calculation took %f s\n' % (endTime - startTime)

Results:


Testing 99194853094755497...

99194853094755497 is prime!

1. Calculation took 202.609000 s

99194853094755497 is prime!

2. Calculation took 114.813000 s

99194853094755497 is prime!

3. Calculation took 28.781000 s

Permanent link to this article: http://ericsilva.org/2009/12/14/primality-test-v2-0/

Leave a Reply