A prime factorization algorithm is any algorithm by which an integer (whole number) is "decomposed" into a product of factors that are prime numbers (Prime factor). The fundamental theorem of arithmetic guarantees that this decomposition is unique. This article gives a simple example of an algorithm, which works well for numbers whose prime factors are small; faster algorithms for numbers with larger prime factors are discussed in the article on integer factorization. A 'fast' algorithm (which can factorise large numbers in a reasonably small time) is much sought after. Flowcharts are often used to represent algorithms. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ... In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. ... In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 is either a prime number or can be written as a product of prime numbers. ... In predicate logic and technical fields that depend on it, uniqueness quantification, or unique existential quantification, is an attempt to formalise the notion of something being true for exactly one thing, or exactly one thing of a certain type. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ...

A simple factorization algorithm

Description

We can describe a recursive algorithm to perform such factorizations: given a number n In mathematics and computer science, recursion specifies (or constructs) a class of objects (or an object from a certain class) by defining a few very simple base cases (often just one), and then defining rules to break down complex cases into simpler cases. ...

• if n is prime, this is the factorization, so stop here.
• if n is composite, divide n by the first prime p₁. If it divides cleanly, recurse with the value n/p₁. Add p₁ to the list of factors obtained for n/p₁ to get a factorization for n. If it does not divide cleanly, divide n by the next prime p₂, and so on.

Note that we need to test only primes p_i such that p_i  ≤  √n.

Example

Suppose we wish to factorize the number 9438.

9438/2 = 4719 with a remainder of 0, so 2 is a factor of 9438. We repeat the algorithm with 4719.

4719/2 = 2359 with a remainder of 1, so 2 is NOT a factor of 4719. We try the next prime, 3.

4719/3 = 1573 with a remainder of 0, so 3 is a factor of 4719. We repeat the algorithm with 1573.

1573/3 = 524 with a remainder of 1, so 3 is NOT a factor of 1573. We try the next prime, 5.

1573/5 = 314 with a remainder of 3, so 5 is NOT a factor of 1573. We try the next prime, 7.

1573/7 = 224 with a remainder of 5, so 7 is NOT a factor of 1573. We try the next prime, 11.

1573/11 = 143 with a remainder of 0, so 11 is a factor of 1573. We repeat the algorithm with 143.

143/11 = 13 with a remainder of 0, so 11 is a factor of 143. We repeat the algorithm with 13.

13/11 = 1 with a remainder of 2, so 11 is NOT a factor of 13. We try the next prime, 13.

13/13 = 1 with a remainder of 0, so 13 is a factor of 13. We stop when we reached 1.

Thus working from top to bottom, we have 9438 = 2 * 3 * 11 * 11 * 13 .

Code

Here is some code in Python for finding the factors of numbers less than 2147483647: Python is an interpreted programming language created by Guido van Rossum in 1990. ...

 import sys 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 more complex code in Python for finding the factors of any arbitrarily large number: Python is an interpreted programming language created by Guido van Rossum in 1990. ...

 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. In mathematics and computer science, a numerical digit is a symbol, e. ... The binary numeral system represents numeric values using two symbols, typically 0 and 1. ...

The difficulty (large time complexity) of factorization makes it a suitable basis for modern cryptography. Cryptography has had a long and colourful history. ...

See also: Euler's Theorem, Integer factorization, Trial division In number theory, Eulers theorem (also known as the Fermat-Euler theorem) states that if n is a positive integer and a is coprime to n, then aφ(n) ≡ 1 (mod n) where φ(n) denotes Eulers totient function. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... Trial division is the simplest and easiest to understand of the integer factorization algorithms. ...

External links

• Prime factorization at Mathworld
• Factorization solver implementing the algorithm described here, work shown
• Factorizer Windows software to decompose numbers up to 2,147,483,646 into their prime constituents.