import random import fractions import os def primality(number, iterations): n = number k = iterations n_=n-1 s=0 d=0 if n <= 1: return False if n == 3 or n == 2: return True if n % 2 == 0: return False while n_ % 2 == 0: s = s + 1 n_= n_/ 2 d = n_ while k != 0: k = k - 1 a = random.randint(2, n-2) x = pow(a,d,n) if x == 1 or x == n - 1: continue r = 1 for r in xrange (1,s): x = pow(x, 2, n) if x == 1: return False elif x == n - 1: break else: return False return True def pollard_brent(number): #returns a factor of an integer where number > 1 is True if number % 2 == 0: return 2 y = random.randint(1,number-1) c = random.randint(1,number-1) m = random.randint(1,number-1) g = 1 r = 1 q = 1 while g == 1: x = y for i in range(r): y = (pow(y,2,number)+c) % number k = 0 while k < r and g == 1: ys = y for i in range(min(m, r-k)): y = (pow(y,2,number)+c) % number q = q*(abs(x-y)) % number g = fractions.gcd(q, number) k = k + m r = r * 2 if g == number: while True: ys = (pow(ys, 2, number)+c) % number g = fractions.gcd(abs(x-ys), number) if g > 1: break return g def prime_factorization(number, iterations): n = number primefactors = [] while primality(number, iterations) == False: if number == 1: break factor = pollard_brent(number) primefactors.append(int(factor)) number = number / factor if number != 1 and n != number: primefactors.append(int(number)) return primefactors n = input('input number to test') k = input('input iterations') print sorted(prime_factorization(n,k)) os.system('pause')