Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Prime factorization algorithm

1 A simple factorization algorithm

1.1 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 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.

1.2 Example

Suppose we wish to factorize 9438. 9438/2 = 4719, with no remainder so 2 is a factor. We repeat the algorithm with 4719. 4719/2 = 2359.5, so 2 is not a factor. 4719/3 = 1573, so 3 is a factor. The first prime number which 1573 is divisible by is 11. 1573/11 = 143. Similarly the first prime number which 143 is divisible by is 11. 143/11 = 13. 13 is itself a prime.

Thus working back, we have 9438 = 2*3*11*11*13

Here is the example in Python:

output:

1.3 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

2 External link

• Prime factorization at Mathworld

Politics	Business	Finance

Topics: Prime Factorization Algorithm Primes Number Candidate Factor...

---

PrimerThis article is about molecular biology for alternate uses, see primer (disambiguation). A primer is a nucleic acid strand (or related molecule) that serves as a starting point for DNA replication. A primer is required because most DNA polymerases ( enzym Prime numberIn mathematics, a prime number or prime for short, is a natural number whose only distinct positive divisors are 1 and itself; otherwise it is called a composite number . Hence a prime number has exactly two divisors. The number 1 is neither prime nor com Prime number theoremIn number theory, the prime number theorem PNT describes the approximate, asymptotic distribution of the prime numbers. For any positive real number x define : The prime number theorem then states that : where ln x is the natural logarithm of x''. This no Prime MinisterAlternate meaning: Prime Minister (band #A prime minister is the leading member of the cabinet of the top level government in a parliamentary system of government of a country, alternatively #A prime minister is an official in a presidential system or sem Prime Minister of AustraliaThe office of Prime Minister is in practice the most powerful political office in the Commonwealth of Australia. By convention, the Prime Minister is the leader of the party or coalition which has the most seats in the lower house of the Federal Parliamen Prime Minister of CanadaThe Prime Minister of Canada the head of the Canadian government, is usually the leader of the political party with the most seats in the Canadian House of Commons. The Prime Minister has the right to the style of Right Honourable''. The current prime min Prime Minister of the United Kingdom Prime Minister of India Prime Minister of Japan Prime Minister of Israel Prime ideal Prime time Prime Directive Prime Meridian Primera, Texas