Prime factorization algorithm
A prime factorization algorithm is any algorithm (a step-by-step process) by which an integer (whole number) is "decomposed" into a product of factorss that are prime numbers. The fundamental theorem of arithmetic guarantees that this decomposition is unique.
A simple factorization algorithm
Description We can describe a recursive algorithm to perform such factorizations:
given a number n if n is prime, this is the factorization, so stop here. if n is composite, divide n by the first prime p1. If it divides cleanly, recurse with the value n/p1. Add p1 to the list of factors obtained for n/p1 to get a factorization for n. If it does not divide cleanly, divide n by the next prime p2, and so on. Note that we need to test only primes pi such that pi ≤ √n.
Example
:Suppose we wish to factorize the number 9438. - 9438/2 = 4719 with a remainder of 0, so 2 is a factor. We repeat the algorithm with 4719.
:4719/2 = 2359 with a remainder of 1, so 2 is NOT a factor.
:4719/3 = 1573 with a remainder of 0, so 3 is a factor. We repeat the algorithm with 1573.
:The first prime number which 1573 is divisible by is the prime number 11.
:1573/11 = 143 with a remainder of 0, so 11 is a factor. We repeat the algorithm with 143.
:Similarly 11 is the first prime number which 143 is divisible by.
:143/11 = 13 with a remainder of 0, so 11 is a factor. We repeat the algorithm with 13.
:13/13 = 1 with a remainder of 0, so 13 is a factor. We stop when we reached 1.
Thus working from top to bottom, we have 9438 = 2*3*11*11*13
Code
Here is the code in Python for finding the factors of numbers less than 2147483647:
from math import sqrt
def factorize(n):
def isPrime(n):
return not [x for x in xrange(2,int(sqrt(n))+1)
if n%x 0]
primes = []
candidates = xrange(2,n+1)
candidate = 2
while not primes and candidate in candidates:
if n%candidate 0 and isPrime(candidate):
primes = primes + [candidate] + factorize(n/candidate)
candidate += 1
return primes
print factorize(int(sys.argv[1]))
output:
python factorize.py 9438
[2, 3, 11, 11, 13]
Here is a more complex code in Python for finding the factors of any arbitrarily large number:
import sys
ListOfPrimes=[2,3,5,7,11,13,17,19]
maxindex=len(ListOfPrimes)
maxprimeinlist=ListOfPrimes[-1]
- Put Primes in a dictionary
DictPrime={}
DictPrime.fromkeys(ListOfPrimes,True)
def intsqrt(n):""" Return the integer square root of a long number """
def intsqrt_core(digitpair,remainder,results):
# function intsqrt_core returns (results,remainder)
if digitpair<100:
currvalue=remainder*100 + digitpair
for d in range(9,-1,-1):
x=(2*10*results + d)*d
if x <= currvalue:
remainder= currvalue - x
results=results*10 + d
return(results,remainder)
else:
(results,remainder)=intsqrt_core(digitpair//100,remainder,results)
(results,remainder)=intsqrt_core(digitpair%100,remainder,results)
return(results,remainder)
(results,remainder)=intsqrt_core(n,0,0)
return results
def isPrime(n):""" Return True if n is a prime """
if DictPrime.has_key(n):
return True
high=intsqrt(n)
for x in ListOfPrimes:
if x <= high and n%x 0:
return False
if x >= high:
return True
x=maxprimeinlist + 2
while x<=high:
if n%x 0:
return False
x += 2
return True
def factorize(n):""" Factorize a integer number """
primes = []
index=0
candidate = ListOfPrimes[index]
while not primes and candidate <= n:
if n%candidate == 0 and (index < maxindex or isPrime(candidate)):
primes = primes + [candidate] + factorize(n//candidate)
index += 1
if index < maxindex:
candidate = ListOfPrimes[index]
else:
candidate += 2
return primes
def condense(L):""" Condense result in list to prime^nth_power format """
prime,count,list=0,0,[]
for x in L:
if x == prime:
count += 1
else:
if prime != 0:
list = list + [str(prime) + '^' + str(count)]
prime,count=x,1
list = list + [str(prime) + '^' + str(count)]
return list
if __name__ == '__main__':
print condense(factorize(long(sys.argv[1])))
- Sample output
- python factorize.py 173248246132375748867198458668657948626531982421875
- ['3^24', '5^14', '7^33', '13^1']
Time complexity
The algorithm described above works fine for small n, but becomes impractical as n gets larger. For example, for an 18-digit (or 60 bit) number, all primes below about 1,000,000,000 may need to be tested, which is taxing even for a computer. Adding two decimal digits to the original number will multiply the computation time by 10. The difficulty (large time complexity) of factorization makes it a suitable basis for modern cryptography. See also: Euler's Theorem, Integer factorization, Trial division
External link Prime factorization at Mathworld
|
|
