Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Find the Prime Factorization of a Number

Every whole number greater than 11 is a product of primes in exactly one way. Divide out the smallest prime that fits, again and again, until the quotient is 11.

Recognize the task

You need the building blocks of a number: to find a GCD or LCM, to simplify a fraction, to count divisors. Typical wording: "write 360360 as a product of primes", "factor 1,0011{,}001 completely", an answer like 23⋅32⋅52^3 \cdot 3^2 \cdot 5. Test: a number with no prime factor up to its square root is itself prime, so you never need to try beyond n\sqrt{n}.
Primes are defined in prime numbers, and the uniqueness of the factorization is explained in prime factorization on the divisibility lesson.

Two ways to do it

Repeated divisionusual
n=p1a1⋅p2a2⋯pkakn = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}
Divide by 2,3,5,7,…2, 3, 5, 7, \ldots in order, spotting each prime with the divisibility rules.
Factor treeany split
n=a⋅b, then split a and bn = a \cdot b, \ \text{then split } a \text{ and } b
Split the number into any two factors and keep splitting until every branch ends in a prime; by the Fundamental Theorem of Arithmetic every tree ends with the same primes.

Steps

StepOn n=1,260n = 1{,}260
1Test the smallest prime, 2. The last digit 00 is even, so 22 divides the number.Divisibility rule for 2 ↗1260=2⋅6301260 = 2 \cdot 630
2Divide out that prime as often as it fits. Keep dividing the quotient by the same prime until it no longer divides.630=2⋅315630 = 2 \cdot 315, and 315315 is odd: 1260=22⋅3151260 = 2^2 \cdot 315
3Move to the next prime, 3. The digit sum of 315315 is 99, so 33 divides it; the quotient 105105 has digit sum 66, so 33 divides again.Digit-sum rule for 3 ↗315=32⋅35315 = 3^2 \cdot 35: 1260=22⋅32⋅351260 = 2^2 \cdot 3^2 \cdot 35
4Continue until the quotient is prime. The number 3535 ends in 55, and 35÷5=735 \div 5 = 7 is prime.Divisibility rule for 5 ↗1260=22⋅32⋅5⋅71260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7
5Multiply back to check. The product of the prime powers must give the original number.4⋅9⋅35=12604 \cdot 9 \cdot 35 = 1260

Worked examples

Example 1 · a small number

two steps
84=2⋅42=22⋅2184 = 2 \cdot 42 = 2^2 \cdot 21
halve twice
21=3⋅721 = 3 \cdot 7
digit sum 33
84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7
collect the primes

Example 2 · repeated primes

exponents
360=23⋅45360 = 2^3 \cdot 45
halve three times
45=32⋅545 = 3^2 \cdot 5
digit sum 99, then ends in 55
360=23⋅32⋅5360 = 2^3 \cdot 3^2 \cdot 5
collect the primes

Example 3 · larger prime factors

beyond 5
1,0011{,}001: odd, digit sum 22, ends in 11
no 22, 33 or 55
1001=7⋅1431001 = 7 \cdot 143
try the next prime, 77
143143: 3−4+1=03 - 4 + 1 = 0, so 143=11⋅13143 = 11 \cdot 13
alternating sum for 1111
1001=7⋅11⋅131001 = 7 \cdot 11 \cdot 13
all factors prime
Check a factorization with the prime calculator, or find which small primes divide a number with the divisibility calculator.

See it happen

Picture the number as a block that you keep cutting into equal pieces. Each cut by a prime makes the block smaller, and a prime block cannot be cut any further. Because you always cut by the smallest prime that fits, no prime is skipped and the primes come out in increasing order. The pieces you removed, multiplied together, rebuild the original number, and any other way of cutting ends with exactly the same pieces.

Common mistakes

Stopping at a composite factor

✗ 360=23⋅45360 = 2^3 \cdot 45
✓ 45=32⋅545 = 3^2 \cdot 5, so 360=23⋅32⋅5360 = 2^3 \cdot 3^2 \cdot 5

Writing each prime only once

✗ 72=2⋅372 = 2 \cdot 3
✓ 72=23⋅3272 = 2^3 \cdot 3^2: check 8⋅9=728 \cdot 9 = 72

Testing far past the square root

✗ to show 9797 is prime, try every number up to 9696
✓ try the primes up to 97<10\sqrt{97} < 10: 2,3,5,72, 3, 5, 7 all fail, so 9797 is prime

Listing 1 as a prime factor

✗ 84=1⋅22⋅3⋅784 = 1 \cdot 2^2 \cdot 3 \cdot 7
✓ 11 is not prime: 84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7