Prime factorization
Prime factorization calculator
Break a whole number of up to 100 digits into its prime factors. See the exponent form, a factor tree and the division ladder.
360 = 23 × 32 × 5
Factor tree
Division ladder
- 360 ÷ 2 = 180
- 180 ÷ 2 = 90
- 90 ÷ 2 = 45
- 45 ÷ 3 = 15
- 15 ÷ 3 = 5
- 5 is prime
How the factors are found
Every whole number above 1 is a product of primes in exactly one way, apart from the order. That is the fundamental theorem of arithmetic, and it is why a factorization is worth writing down. The calculator finds it in two stages.
Trial division divides by 2, 3, 5, 7 and every prime up to 100,000, as many times as each one goes in. That finishes most everyday numbers: anything left over below 1010 has no small factor, so it must be prime.
Pollard's rho handles what remains. It repeats x → x² + c (mod n). Taken modulo an unknown prime factor p, those values start repeating after roughly √p steps, and the greatest common divisor of n with the difference of two values then reveals p. This page uses Brent's faster version. Factors of up to about 15 digits appear within a second; a product of two 30-digit primes is beyond any browser, and its unsplit part is shown in brackets.
Worked example
Halve 360 three times (360, 180, 90, 45), divide by 3 twice (15, 5) and 5 is left: 360 = 23 × 32 × 5. The tree reaches the same primes another way, splitting 360 into 18 × 20 and each branch again until only primes hang at the ends.
Sources
- Pollard JM. A Monte Carlo method for factorization. BIT 15 (1975), 331–334, and Brent RP. An improved Monte Carlo factorization algorithm. BIT 20 (1980), 176–184; summarised in Pollard's rho algorithm.
- Fundamental theorem of arithmetic (Euclid, Elements VII.30 and IX.14; Gauss, Disquisitiones Arithmeticae, 1801).
- Cole FN. On the factoring of large numbers. Bulletin of the American Mathematical Society 10 (1903), 134–137.
Questions
Is there only one factor tree for a number?
No. 360 can start as 18 × 20, 10 × 36 or 2 × 180. Every tree ends with the same primes, 2, 2, 2, 3, 3 and 5, which is exactly what the fundamental theorem of arithmetic promises.
Why does part of a big number stay in brackets?
Pollard's rho needs about √p steps to find a prime factor p. A 25-digit factor would take trillions of steps. The bracketed part is known to be composite but needs heavier methods, such as the elliptic curve method or the number field sieve.
What is special about 2^67 − 1?
Mersenne listed it as prime in 1644. In 1903 Frank Nelson Cole showed it equals 193,707,721 × 761,838,257,287, reportedly multiplying both sides out on a blackboard without saying a word. This calculator splits it in a fraction of a second.