---
title: "Prime Factorization Calculator & Factor Tree | Prime Orchard"
description: "Break any whole number into primes with exponents, a drawn factor tree and the division ladder. Big numbers use Pollard's rho, right in your browser."
url: https://primeorchard.top/prime-factorization/
---

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.

## 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](https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm).
- [Fundamental theorem of arithmetic](https://en.wikipedia.org/wiki/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.