Tuesday, May 24, 2011

Python - Determine Primality of a number

 
# Determining primality by using a simple trial division test. 
# 
# This approach tests whether n is a multiple of an integer i 
# between 2 and √n.  If it is a multiple of any of these integers 
# then it is not a prime. 
 
import math
import time
 
def isPrime(n):
    for i in range(2, int(math.sqrt(n))):
        if n % i == 0:
            return False
    return True
 
def withTimer(n):
    start = time.time()
    prime = isPrime(n)
    elapsed = time.time() - start
    print("{0}   {1}    time:{2}").format(prime, n, elapsed)
 
# Primality of 2 to 13 digit known primes 
withTimer(13)
withTimer(715827883)
withTimer(2932031007403)
 
# test non primes 
withTimer(52)
withTimer(5820384023)
withTimer(2059384726303)
 
# my output: 
# True   13    time:0.0 
# True   715827883    time:0.00300002098083 
# True   2932031007403    time:0.521000146866 
# False   52    time:0.0 
# False   5820384023    time:0.000999927520752 
# False   2059384726303    time:0.029000043869