# 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.
Showing posts with label prime. Show all posts
Showing posts with label prime. Show all posts
Tuesday, May 24, 2011
Python - Determine Primality of a number
Subscribe to:
Posts (Atom)