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 6*k* ± 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.

''' 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

## Recent Comments