What is prime factorization?
Prime factorization (also called integer factorization or prime decomposition) breaks a positive integer down into the prime numbers that multiply together to make it. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has exactly one such factorization, ignoring order. This calculator finds those primes for any whole number from 2 up to just under 10 trillion (13 digits) and presents them four ways: as a product, in exponential form, as a CSV list, and as an optional factor tree.
Which prime number tool do you need?
- Prime number checker: whether a number is prime, with the previous and next prime.
- Prime number calculator: whether a number is prime and its smallest factor other than 1.
- Nth prime: the nth prime, or a list of the first N primes.
- Prime factorization (this page): the prime factors of a number, with a factor tree.
- Relatively prime: whether two numbers are coprime (no common factor other than 1).
How to use it
Type a positive integer greater than 1 into the box and submit. Tick "create a factorization tree" if you want a visual breakdown. The result shows the prime factors written out (e.g. 2 x 2 x 5 x 5), the compact exponential form (2^2 x 5^2), a comma-separated list, the count of distinct primes, the total number of prime factors counted with multiplicity, and the prime index Prime[n] for any factor among the first 5000 primes.
The formula and algorithm
The tool uses trial division. It first removes all factors of 2, then tests odd divisors 3, 5, 7, ... while the divisor squared is no larger than the remaining value. Each time a divisor divides evenly it is recorded and divided out. Whatever is left greater than 1 at the end is itself a prime factor. Testing only up to the square root works because any composite number must have a factor at or below its square root.
$$\text{Number} = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$$
Worked example: n = 100
\(100 / 2 = 50\), \(50 / 2 = 25\), so two 2s. Then 25 is not divisible by 3 but is divisible by 5: \(25 / 5 = 5\), \(5 / 5 = 1\), giving two 5s. The factors are 2, 2, 5, 5. As a product that is 2 x 2 x 5 x 5, in exponential form 2^2 x 5^2. There are 2 distinct primes and 4 total prime factors. Check: $$2 \times 2 \times 5 \times 5 = 100$$ Prime indices: \(2 = \text{Prime}[1]\), \(5 = \text{Prime}[3]\).
Interpreting Your Result
- Prime or composite: if the only factor is \(n\) itself (\(n = n^1\)), the number is prime. Two or more prime factors, counting repeats, mean it is composite. The number 1 has no prime factors and is neither prime nor composite.
- Perfect powers: if every exponent is even, \(n\) is a perfect square (for example \(36 = 2^2 \times 3^2\)). If every exponent is a multiple of 3, it is a perfect cube (for example \(1000 = 2^3 \times 5^3\)).
- Number of divisors: for \(n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\), the count is \((e_1+1)(e_2+1)\cdots(e_k+1)\). For example, \(100 = 2^2 \times 5^2\) has \((2+1)(2+1) = 9\) divisors: 1, 2, 4, 5, 10, 20, 25, 50, 100.
- Distinct primes vs. multiplicity: 360 has 3 distinct primes (2, 3, 5) but 6 prime factors when repeats are counted. Always check which count you need.
- GCD and LCM: the GCD takes the minimum exponent of each prime and the LCM takes the maximum. For \(84 = 2^2 \cdot 3 \cdot 7\) and \(360 = 2^3 \cdot 3^2 \cdot 5\): \(\gcd = 2^2 \cdot 3 = 12\) and \(\operatorname{lcm} = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520\). Check: \(12 \times 2520 = 30240 = 84 \times 360\).
- Simplifying fractions: cancel the shared primes. For \(\tfrac{84}{360}\), cancel \(2^2 \cdot 3 = 12\) to get \(\tfrac{7}{30}\).
Reference Table: Small Primes and Common Factorizations
The first 25 primes
| n | Prime[n] | n | Prime[n] | n | Prime[n] | n | Prime[n] | n | Prime[n] |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 13 | 11 | 31 | 16 | 53 | 21 | 73 |
| 2 | 3 | 7 | 17 | 12 | 37 | 17 | 59 | 22 | 79 |
| 3 | 5 | 8 | 19 | 13 | 41 | 18 | 61 | 23 | 83 |
| 4 | 7 | 9 | 23 | 14 | 43 | 19 | 67 | 24 | 89 |
| 5 | 11 | 10 | 29 | 15 | 47 | 20 | 71 | 25 | 97 |
Common factorizations
| Number | Prime factorization | Number of divisors |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 24 | 2³ × 3 | 8 |
| 36 | 2² × 3² | 9 |
| 48 | 2⁴ × 3 | 10 |
| 60 | 2² × 3 × 5 | 12 |
| 72 | 2³ × 3² | 12 |
| 120 | 2³ × 3 × 5 | 16 |
| 144 | 2⁴ × 3² | 15 |
| 180 | 2² × 3² × 5 | 18 |
| 360 | 2³ × 3² × 5 | 24 |
| 720 | 2⁴ × 3² × 5 | 30 |
| 1000 | 2³ × 5³ | 16 |
| 1024 | 2¹⁰ | 11 |
Divisibility rules
| Divisor | Rule |
|---|---|
| 2 | The last digit is 0, 2, 4, 6 or 8. |
| 3 | The sum of the digits is divisible by 3. |
| 5 | The last digit is 0 or 5. |
| 7 | Double the last digit and subtract it from the rest of the number. If the result is divisible by 7, so is the original (343: 34 − 6 = 28, yes). |
| 11 | The alternating sum of the digits is divisible by 11 (121: 1 − 2 + 1 = 0, yes). |
FAQ
What about the number 1? The number 1 is neither prime nor composite and has no prime factors, so the calculator reports that special case.
What if my number is prime? A prime number such as 13 has itself as its only prime factor; the exponential form is just 13.
How big a number can I factor? Up to nearly 10 trillion. Numbers near that limit with a large prime factor may take a moment, since trial division checks divisors up to the square root.