# 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
A python example based blog that shows how to accomplish python goals and how to correct python errors.
Tuesday, May 24, 2011
Python - Determine Primality of a number
Subscribe to:
Post Comments (Atom)
For a very quick and obvious speedup, check for divisibility by 2 first, then check for divisibility by odd numbers from 3 to sqrt(n).
ReplyDelete