Prime Factorization

Breaking a Number Down Into Its Prime Building Blocks

Every whole number greater than 1 can be broken down into a unique set of prime numbers multiplied together — its prime factorization. Enter a whole number, and this calculator finds that factorization instantly, along with whether the number itself is prime.

The Formula

The Fundamental Theorem of Arithmetic guarantees every whole number N greater than 1 has exactly one prime factorization, up to the order the factors are written in:

$$\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}$$

where each $\vB{p_i}$ is a distinct prime number and each $\vC{a_i}$ is how many times that prime divides evenly into N.

This calculator finds that factorization using trial division: starting at 2, it repeatedly checks whether each number divides evenly into what’s left, dividing it out (and counting how many times) whenever it does, then moving to the next candidate. Once a candidate’s square exceeds what remains, anything still left over must itself be prime — any smaller factor would already have been found:

$$\text{if } \vD{d}^2 > \vE{\text{remaining value}}, \text{ then } \vE{\text{remaining value}} \text{ is prime}$$

Worked Example

Finding the prime factorization of 360:

1. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2 divides in 3 times; 45 is odd, so move on).
2. 45 ÷ 3 = 15, ÷ 3 = 5 (3 divides in 2 times; 5 isn’t divisible by 3 again).
3. 5 remains, and no further divisor’s square is ≤ 5, so 5 itself is prime.
4. Result: 2³ × 3² × 5.

Key Factors to Consider

• Every prime factorization is unique — this is exactly what the Fundamental Theorem of Arithmetic guarantees. No matter how a number is broken down, its prime factorization always comes out the same (aside from the order the factors are written in), which is why prime factorization is such a fundamental building block across number theory.
• Prime factorization is the mechanism behind finding a Greatest Common Factor or Least Common Multiple by hand. Comparing two numbers’ prime factorizations directly reveals their GCF (the shared prime factors, at the lower shared exponent) and LCM (every prime factor, at the higher exponent) — see the GCF/LCM Calculator for that specific comparison.
• Factoring large numbers gets computationally much harder as the number of digits grows, which is the basis for some encryption methods. Trial division (the method used here) works well for numbers people typically enter by hand, but factoring a very large number with hundreds of digits can be computationally infeasible even for powerful computers — this difficulty is exactly what underlies RSA encryption’s security.
• A prime number has exactly one prime factor: itself, to the first power. This is why this calculator’s “is this number prime” check falls directly out of the factorization process — if trial division never finds a factor smaller than the number’s own square root, the number has no factorization other than itself.

Common Mistakes

• Confusing prime factorization with a full list of factors. 12’s factors are 1, 2, 3, 4, 6, and 12, but its prime factorization is only 2² × 3 — prime factorization keeps only the prime building blocks, not every number that divides evenly.
• Treating 1 as a prime number. By definition a prime number has exactly two distinct divisors (1 and itself) — 1 has only one, so it’s neither prime nor composite and never appears in a prime factorization.
• Losing track of repeated prime factors. 8’s prime factorization is 2³, not just “2” — forgetting how many times a prime divides in changes the number the factorization actually represents.

Useful to Know

• Need the Greatest Common Factor or Least Common Multiple of two numbers instead of one number’s own factors? Greatest Common Factor and Least Common Multiple Calculator compares two numbers’ prime factorizations directly.
• Simplifying a fraction to its lowest terms? Fraction Calculator uses the same shared prime factors this calculator finds.
• Working with a very large or very small number instead? Scientific Notation Calculator converts between standard and scientific notation.