math.wiki
Number › Divisibility and primes › Prime factorization
Open on the map
Math 6

Prime factorization

A mosaic artist can lay 132 square tiles as a rectangle in several ways. If you keep splitting 132 into smaller factors, what is it made of in the end?

You need
Prime and composite numbersGrade 4Exponent notationGrade 6
Unlocks
Every number has exactly one prime factorizationMath 6Finding them from prime factorizationsMath 6Greatest common factor and least common multipleGrades 5 to 6Which fractions give terminating decimalsMath 8Simplifying a square rootAlgebra 1Simplifying radicalsGrade 9+3 more
Where you are 10 in Divisibility and primes
Number9
Divisibility and primes10
▴ 3 abovePerfect, abundant, deficient and amicable numbersPrime and composite numbers
Prime factorization
Tests for three and nineThe sieve of Eratosthenes▾ Show all 10 (2 more)

When you reach for it

Folake makes mosaics from square tiles, and she lays each batch as a full rectangle, with no gaps and no tiles left over. A rectangle of tiles holds its number of rows times its number of columns, so every rectangle she can make from a batch is a factor pair of the number of tiles. Twenty-four tiles can be 1 by 24, 2 by 12, 3 by 8 or 4 by 6. Seven tiles can only be a single strip, 1 by 7, because 7 is a prime number: its only factors are 1 and itself.

24 = 4 \cdot 6
7 = 1 \cdot 7
Figure 1Every rectangle of tiles is a factor pair. Seven tiles make only a strip, because 7 is prime.

A factor pair is a way to split a number, and the pieces can be split again. Since 4 = 2 \cdot 2 and 6 = 2 \cdot 3,

24 = 4 \cdot 6 = 2 \cdot 2 \cdot 2 \cdot 3

Now no piece splits any further, because 2 and 3 are prime. Writing a whole number greater than 1 as a product of primes is finding its prime factorization. A prime that repeats is written with an exponent, so the prime factorization of 24 is 2^3 \cdot 3. A prime is its own prime factorization: the factorization of 7 is just 7.

Reach for it whenever you need to know what a number is built from. This lesson gives two ways to find the primes: the factor tree (Part 1) and the ladder (Part 2). Later lessons use the result to list every factor of a number, to compare two numbers, and to simplify square roots.

The procedure

Part 1: factor trees

Start with any factor pair. Write the number at the top. Below it, write two factors whose product is the number, neither of them 1, and join each to the number with a branch. For 132, Yuki starts with 6 and 22. This is allowed because 6 \cdot 22 is 132: a split changes how the number is written, not its value. The pair 1 \cdot 132 is ruled out because it splits nothing; the 132 comes back unchanged.

Circle the primes and split the rest. A prime cannot be split into two factors without using 1, so its branch ends there, and it is circled. A composite number has a factor pair without 1, so it is split the same way. Here 6 = 2 \cdot 3 and 22 = 2 \cdot 11, and all four are prime.

132 6 22 2 3 2 11
132 = 2^2 \cdot 3 \cdot 11
Figure 2A factor tree for 132. The circled primes multiply back to the number at the top.

Read the circled numbers. Each split replaced a number by a product equal to it, so the circled numbers multiply back to the top number: 132 = 2 \cdot 3 \cdot 2 \cdot 11.

Put them in order and use exponents. Multiplication can be done in any order (the commutative property) and grouped any way (the associative property), so the primes may be listed smallest first and the repeats gathered together. Then 2 \cdot 2 is written 2^2. An exponent of 1 is not written.

132 = 2 \cdot 2 \cdot 3 \cdot 11 = 2^2 \cdot 3 \cdot 11

Check by multiplying. 2^2 \cdot 3 \cdot 11 = 4 \cdot 33 = 132. A correct answer passes two tests: every number in it is prime, and the product is the number you started with.

Why the tree always ends. In a split without 1, each factor is at least 2, so the other factor is at most half the number. Every number on the tree is therefore smaller than the one above it. Whole numbers cannot keep getting smaller forever, so each branch reaches a number that cannot be split, and that number is a prime.

Finding a first split. Any factor pair will do, so take whichever is easiest to see. The last-digit tests say when 2, 5 or 10 is a factor, and the digit-sum tests say when 3 or 9 is.

Different trees, same primes. Mateus and Idris both factor 168. Mateus starts with 6 \cdot 28, and Idris starts with 14 \cdot 12.

168 6 28 2 3 2 14 2 7
2^3 \cdot 3 \cdot 7
 168 14 12 2 7 2 6 2 3
2^3 \cdot 3 \cdot 7
Figure 3Two different first splits of 168. Both trees end in the same primes, 2^3 \cdot 3 \cdot 7.

The trees look different, but both end in three 2s, one 3 and one 7, so both give 168 = 2^3 \cdot 3 \cdot 7. This is no accident. Whichever split you start with, a number always comes out with the same primes, each appearing the same number of times. Why that must happen is the subject of the next lesson. For now it means you may start a tree any way you like and still reach the one right answer.

Part 2: the ladder

The ladder, also called repeated division, finds the same primes by dividing instead of splitting.

Divide by the smallest prime that goes in. Try 2, then 3, then 5, then 7, and so on through the primes. Write the prime on the left and the quotient underneath. For 240, the prime 2 goes in, and 240 \div 2 = 120.

Try the same prime again before moving on. 120 \div 2 = 60, then 60 \div 2 = 30, then 30 \div 2 = 15. Now 15 is odd, so 2 no longer goes in, and the next prime is tried: 15 \div 3 = 5. Then 5 \div 5 = 1.

Stop at 1. The primes down the left side are the prime factorization.

240 2 120 2 60 2 30 2 15 3 5 5 1
240 = 2^4 \cdot 3 \cdot 5
Figure 4The ladder for 240. The primes down the left side are its prime factorization.
240 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 = 2^4 \cdot 3 \cdot 5

Why it works. Each line of the ladder says that its number equals the prime beside it times the number below. So 240 = 2 \cdot 120 = 2 \cdot 2 \cdot 60, and so on down: at every stage, 240 equals the primes so far times the number at the bottom. When the bottom is 1, 240 equals the product of the primes on the left. Each divisor is prime because only primes are tried, and they come out already in order, so the exponents are found by counting.

Some people stop one line earlier, when the quotient is itself prime, and include that prime in the product. The answer is the same; stopping at 1 makes sure the last prime is not forgotten.

When to stop trying primes. Sometimes no small prime divides a quotient, and you must decide whether it is prime. Suppose 2, 3, 5 and 7 all fail on a number. Then any factor of it other than 1 also avoids 2, 3, 5 and 7, and the smallest whole number above 1 that does so is 11. A factor pair without 1 would then be at least 11 \cdot 11 = 121. So a number below 121 on which 2, 3, 5 and 7 all fail is prime. In general, you need to try only the primes whose square is no bigger than the number, the same stopping rule the sieve of Eratosthenes uses.

Tree or ladder? The tree is quicker when a split jumps out, such as a number ending in 0. The ladder is steadier when nothing obvious divides, and it hands over the primes in order. Both give the same factorization.

Worked examples

Examples 1 to 3 go with Part 1. Examples 4 to 6 go with Part 2.

Example 1

A first factor tree

Mateus has 90 tiles. Find the prime factorization of 90 with a factor tree.

Solution

90 ends in 0, so 10 is a factor: 90 = 9 \cdot 10. Neither is prime, so both split again: 9 = 3 \cdot 3 and 10 = 2 \cdot 5. Every branch now ends in a prime, and the circled numbers are 3, 3, 2 and 5. Smallest first, with the two 3s written as a power:

90 = 2 \cdot 3 \cdot 3 \cdot 5 = 2 \cdot 3^2 \cdot 5

Check. 2 \cdot 9 \cdot 5 = 90.

Example 2

A prime used many times

Anders has 162 tiles. Find the prime factorization of 162.

Solution

162 is even, so 162 = 2 \cdot 81, and the 2 is circled. The digits of 81 add to 9, so 9 is a factor: 81 = 9 \cdot 9. Each 9 splits as 3 \cdot 3. The circled numbers are one 2 and four 3s:

162 = 2 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = 2 \cdot 3^4

The exponent counts the 3s: 3^4 means 3 \cdot 3 \cdot 3 \cdot 3 = 81, not 3 \cdot 4. Check. 2 \cdot 81 = 162.

Example 3

Reading a rectangle from the primes

Folake has 462 tiles. Find the prime factorization of 462, and use it to find a rectangle she can make with one side 21 tiles long.

Solution

462 is even: 462 = 2 \cdot 231. The digits of 231 add to 6, so 3 is a factor: 231 = 3 \cdot 77. And 77 = 7 \cdot 11, both prime.

462 = 2 \cdot 3 \cdot 7 \cdot 11

Each prime appears once, so no exponents are needed.

Sorting the primes into two groups splits 462 into a factor pair, again by the commutative and associative properties. Since 21 = 3 \cdot 7, put 3 and 7 in one group. The other group is 2 \cdot 11 = 22, so Folake can lay a rectangle 21 tiles by 22 tiles. Check. 21 \cdot 22 = 462.

Example 4

A ladder

Idris has 616 tiles. Find the prime factorization of 616 with the ladder.

Solution

Start with 2 and keep dividing while it goes in: 616 \div 2 = 308, 308 \div 2 = 154 and 154 \div 2 = 77. Now 77 is odd, so move on. Its digits add to 14, so 3 does not go in, and it does not end in 0 or 5, so neither does 5. Next is 7: 77 \div 7 = 11. Then 11 \div 11 = 1, and the ladder stops.

Divide byNumber
2616
2308
2154
777
1111
1

The left column holds three 2s, one 7 and one 11:

616 = 2^3 \cdot 7 \cdot 11

Check. 8 \cdot 77 = 616.

Example 5

When no split is easy to see

Mei has 598 tiles. Find the prime factorization of 598.

Solution

598 \div 2 = 299. Now 299 is odd, its digits add to 20 so 3 fails, and it does not end in 0 or 5. Try 7: 7 \cdot 42 = 294, which leaves 5. Try 11: 11 \cdot 27 = 297, which leaves 2. Try 13: 13 \cdot 23 = 299, so 299 \div 13 = 23.

Is 23 prime? Only primes whose square is at most 23 need trying, and those are 2 and 3, since 5 \cdot 5 = 25 is already too big. Neither divides 23, so 23 is prime, and 23 \div 23 = 1.

598 = 2 \cdot 13 \cdot 23

The ladder suits this number: no factor pair of 299 is easy to spot, and trying the primes in order is sure to find one.

Example 6

A square of tiles

Anders wants to lay 1764 tiles as a square. Use the prime factorization of 1764 to decide whether he can, and find the side.

Solution

The ladder: 1764 \div 2 = 882 and 882 \div 2 = 441. Then 441 is odd and its digits add to 9, so 441 \div 3 = 147 and 147 \div 3 = 49. Finally 49 is not divisible by 3 or 5, and 49 \div 7 = 7, 7 \div 7 = 1.

1764 = 2^2 \cdot 3^2 \cdot 7^2

Every exponent is even, so the primes share out into two identical groups, one of each pair in each group:

1764 = (2 \cdot 3 \cdot 7) \cdot (2 \cdot 3 \cdot 7) = 42 \cdot 42

So Anders can lay a square 42 tiles on each side.

Compare 175 = 5^2 \cdot 7. A single 7 cannot be shared equally between two groups. A square n \cdot n would give every prime of n twice, so its exponents are all even, and since the primes of 175 always come out the same (Every number has exactly one prime factorization), 175 is not a square. Indeed 13 \cdot 13 = 169 and 14 \cdot 14 = 196 miss it.

Boundaries

Whole numbers above 1 only. 1 is neither prime nor composite and has nothing to split, so it has no prime factorization. Neither does 0: it equals 0 \cdot 5, 0 \cdot 7 and 0 times anything, so splitting it never reaches a list of primes.

1 never appears in a factorization. It is not prime, and splitting with it makes no progress. It could also be written in any number of times without changing the product.

A prime is its own factorization. The tree for 13 is just 13, circled, and its ladder is one line.

The ladder divides by primes only. Dividing by 4 or 6 would put a composite number on the left. Trying in order from 2 prevents this: by the time 4 is reached, every 2 has already been divided out, so 4 cannot go in.

One factorization, many ways to write it. 2^2 \cdot 3 \cdot 11, 11 \cdot 3 \cdot 2^2 and 3 \cdot 2 \cdot 11 \cdot 2 are the same factorization in different orders. Smallest prime first, with exponents, is a convention that makes two factorizations easy to compare.

Where this goes next

The next lesson shows why the primes always come out the same, the fact Example 6 leaned on, and the fundamental theorem of arithmetic states it in full. With a factorization in hand, listing every factor becomes a matter of choosing some of the primes, as Folake did in Example 3. Two factorizations side by side lead to the greatest common factor and least common multiple, and comparing the powers of each prime finds both. Pairing equal primes, as in Example 6, is how you simplify a square root, and the primes of a denominator decide which fractions give terminating decimals.

Exercises

Part 1: factor trees

Use a factor tree to find the prime factorization. Write it with exponents, smallest prime first.

  1. 18
  2. 40
  3. 70
  4. 98
  5. 135
  6. 196
  7. 264

Part 1: exponents

  1. Write 2^3 \cdot 3^2 \cdot 5 as a whole number.
  2. Write 2 \cdot 3^2 \cdot 7^2 as a whole number.
  3. Write 5 \cdot 2 \cdot 5 \cdot 3 \cdot 5 with exponents, smallest prime first, and find the number.
  4. Yuki starts a factor tree for 210 with 14 and 15. Mateus starts one with 10 and 21. Finish both trees and compare the primes.

Part 2: the ladder

Use the ladder to find the prime factorization.

  1. 64
  2. 275
  3. 348
  4. 1045
  5. 1000
  6. 2310
  7. 221

Part 2: prime or not

  1. Is 187 prime?
  2. Is 211 prime? Say which primes you need to try, and why no others.

Part 2: tiles

  1. Idris has 784 tiles. Use the prime factorization of 784 to show that he can lay them as a square, and find its side.
  2. Mei has 2^4 \cdot 3 \cdot 5^2 tiles. How many tiles is that? She lays them as a rectangle with one side 15 tiles long. How long is the other side?

Reasoning

  1. Explain why a factor tree always comes to an end, however big the number at the top.
  2. Folake says the tree for 7 should be 7 = 1 \cdot 7, with both numbers circled. Explain why a factor tree never uses 1.
  3. On the ladder, 2, 3, 5 and 7 all fail on a number less than 121. Explain why the number must be prime.
Answers
  1. 2 \cdot 3^2. 18 = 2 \cdot 9 and 9 = 3 \cdot 3.
  2. 2^3 \cdot 5. 40 = 4 \cdot 10, 4 = 2 \cdot 2 and 10 = 2 \cdot 5.
  3. 2 \cdot 5 \cdot 7. 70 = 7 \cdot 10 and 10 = 2 \cdot 5.
  4. 2 \cdot 7^2. 98 = 2 \cdot 49 and 49 = 7 \cdot 7.
  5. 3^3 \cdot 5. 135 = 5 \cdot 27 and 27 = 3 \cdot 9 = 3 \cdot 3 \cdot 3.
  6. 2^2 \cdot 7^2. 196 = 4 \cdot 49, 4 = 2 \cdot 2 and 49 = 7 \cdot 7.
  7. 2^3 \cdot 3 \cdot 11. 264 = 8 \cdot 33, 8 = 2 \cdot 2 \cdot 2 and 33 = 3 \cdot 11.
  8. 360. 8 \cdot 9 \cdot 5 = 72 \cdot 5 = 360.
  9. 882. 2 \cdot 9 \cdot 49 = 18 \cdot 49 = 882.
  10. 2 \cdot 3 \cdot 5^3 = 750. The three 5s make 5^3 = 125, and 6 \cdot 125 = 750.
  11. Both give 2 \cdot 3 \cdot 5 \cdot 7. Yuki: 14 = 2 \cdot 7 and 15 = 3 \cdot 5. Mateus: 10 = 2 \cdot 5 and 21 = 3 \cdot 7. The same four primes, as they must be.
  12. 2^6. Dividing by 2 six times gives 32, 16, 8, 4, 2, 1.
  13. 5^2 \cdot 11. 275 is odd and its digits add to 14, so 2 and 3 fail; 275 \div 5 = 55, 55 \div 5 = 11, 11 \div 11 = 1.
  14. 2^2 \cdot 3 \cdot 29. 348 \div 2 = 174, 174 \div 2 = 87, 87 \div 3 = 29, and 29 is prime because 2, 3 and 5 fail and 7 \cdot 7 = 49 is bigger than 29.
  15. 5 \cdot 11 \cdot 19. 1045 is odd and its digits add to 10, so 2 and 3 fail; 1045 \div 5 = 209. Then 5 fails again, 7 fails (7 \cdot 29 = 203 leaves 6), and 209 \div 11 = 19.
  16. 2^3 \cdot 5^3. Dividing by 2 gives 500, 250, 125; dividing by 5 gives 25, 5, 1.
  17. 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11. 2310 \div 2 = 1155, 1155 \div 3 = 385, 385 \div 5 = 77, 77 \div 7 = 11, 11 \div 11 = 1.
  18. 13 \cdot 17. 2, 3, 5, 7 and 11 all fail (7 \cdot 31 = 217 leaves 4, 11 \cdot 20 = 220 leaves 1), and 221 \div 13 = 17.
  19. No. 2, 3, 5 and 7 fail (7 \cdot 26 = 182 leaves 5), but 187 = 11 \cdot 17.
  20. Yes, 211 is prime. Only primes whose square is at most 211 need trying: 2, 3, 5, 7, 11 and 13, since 17 \cdot 17 = 289 is too big. 211 is odd, its digits add to 4, it ends in 1, 7 \cdot 30 = 210 leaves 1, 11 \cdot 19 = 209 leaves 2 and 13 \cdot 16 = 208 leaves 3.
  21. 784 = 2^4 \cdot 7^2, and every exponent is even, so 784 = (2^2 \cdot 7) \cdot (2^2 \cdot 7) = 28 \cdot 28: a square with side 28.
  22. 1200 tiles, and the other side is 80. 16 \cdot 3 \cdot 25 = 1200. Since 15 = 3 \cdot 5, the remaining primes give 2^4 \cdot 5 = 80, and 15 \cdot 80 = 1200.
  23. Every split uses two factors that are each at least 2, so each is at most half the number being split, and smaller than it. Down any branch the numbers keep getting smaller, and whole numbers cannot get smaller forever, so every branch stops. It can stop only at a number that cannot be split without 1, which is a prime.
  24. Splitting 7 as 1 \cdot 7 gives the 7 back unchanged, so it makes no progress, and 1 is not prime, so circling it would put a number that is not prime into the factorization. A prime’s branch simply ends with the prime itself circled.
  25. Suppose the number had a factor pair a \cdot b with neither factor 1. Neither a nor b can be divisible by 2, 3, 5 or 7, or the number would be too. The smallest whole number above 1 that none of them divides is 11, so a and b are each at least 11, and the number is at least 121. That is impossible, so there is no such pair, and the number is prime.
kg1128 · updated 2026-10-12 · CC-BY-SA-4.0