import random import os import time g = input('number from file: 0 | manual input: 1 ') if g == 0: file = open('number.txt', 'r+') print file n = int(file.readline()) file.close() elif g == 1: n = input('number to test: ') number_length = len(str(n)) k = input('number of iterations: ') start = time.time() n_=n-1 #supposed to write n-1 as 2^s*d later; so substitute this instead s=0 d=0 def composite(): end = time.time() print end-start, 'seconds taken' print ' ' if number_length < 1000: print n , 'is composite' #print composite else: print 'number is composite' print ' ' os.system('pause') os.sys.exit() def prime(): end = time.time() print end-start, 'seconds taken' print ' ' if number_length < 1000: print n , 'is prime' #print prime else: print 'number is prime' print ' ' os.system('pause') os.sys.exit() def neither(): end = time.time() print end-start, 'seconds taken' print ' ' if number_length < 1000: print n , 'is neither prime nor composite' else: print 'number is neither prime nor composite' print ' ' os.system('pause') os.sys.exit() if n <= 1: neither() if n == 3 or n == 2: #filters out numbers <= 3 because the primality test can't prime() if n % 2 == 0: composite() while n_ % 2 == 0: #making n_ into 2^s*d s = s + 1 n_= n_/ 2 d = n_ while k != 0: #corresponds to line : LOOP: repeat k times: k = k - 1 a = random.randint(2, n-2) # corresponds to : pick a random integer a in the range from 2 to n minus 2 x = pow(a,d,n) # corresponds to : x = a^d mod n if x == 1 or x == n - 1: #corresponds to : if x = 1 or x = n - 1 then do next loop continue # if this is true then go back to the while k!=0 loop r = 1 for r in xrange (1,s): #do this from r = 1 to r = s - 1 x = pow(x, 2, n) #corresponds to x = x^2 mod n if x == 1: #corresponds to if x = 1 then return composite composite() elif x == n - 1: #if x = n - 1, then it will ignore the if and break and go back to while k!=0 loop break else: composite() #corresponds to return composite; this is the composite that keeps on getting triggered when a prime is tested prime() #return prime