Programming. Technology. Math.

Prime factorization is a common mathematical technique. But just what is prime factorization?

Before we define prime factorization, we will first give a definition of the two components of that phrase separately: “prime” and “factorization”.

A prime number is any positive whole number (i.e. any integer greater than zero) which is only divisible exactly by two whole numbers: itself and one. If you attempt to divide a prime number by any other whole number there will be a remainder left over. The first few prime numbers are 2, 3, 5, 7, 11 and 13. The number 9, for example, isn’t a prime number as it can be divided by 3 with no remainder.

Factorization is essentially the reverse of multiplication. Multiplication combines two or more numbers to find their *product. *Factorization instead takes the product and attempts to recover those original numbers (which we call the *factors**)*. So if we multiply 5*6 to get 30, we could then factorize 30 to get back to 5 and 6.

We can take our example above a little further. Notice that when we factorized 30 we found 5 and 6 as factors. However, 6 is itself the product of two numbers, 3 and 2. So we can factorize 6 to get 3 and 2. This means that if we *fully *factorize 30 we get the following factors: 5, 3 and 2. Notice also that each of these factors is a *prime* number. When we factorize a number and end up with only prime numbers as factors, we say we have the *prime factorization* of the original number.

So the prime factorization of a number is a list of prime numbers which, when multiplied together, produce that number.

It is possible that the same number will appear more than once in the list of prime numbers. For example, 3*3*3=27. However, the *fundamental theorem of arithmetic* tells us that each number has exactly one unique prime factorization. So every number has a prime factorization, and every time we find a prime factorization for a particular number it will consist of the same numbers (though the order of the numbers may have changed).

This is where it gets a bit tricky. While it is relatively easy to multiply numbers together to find their product, it can be more difficult to find a prime factorization.

For small numbers, the prime factorization can be found just by trying out numbers which we think might divide our product without a remainder. When we find one, we split our product into two parts: the number we tried and what is left. We then keep factorizing each part in the same way until we end up with only prime numbers. This gives us our prime factorization.

As an example, find the prime factorization of 75. As it ends in 5, we know that it must be divisible by 5. Since 75/5=15, our new parts are 15 and 5. We know that 5 is a prime number (see the examples of prime numbers above), so we just need to keep factoring 15. It is easy to see that we can divide it by 5 again, so now we have 75=5*5*3 (since 15/5=3). So the prime factorization of 75 is 3,5 and 5 (often written as 3*5*5).

To re-enforce it, let’s do another example – find the prime factorization of 18. As the last digit is even, we know that 18 is divisible by 2. Since 18/2 = 9, we can split 18 into 9 and 2. We know 2 is prime, so we just need to further split 9. We know, of course, that 9=3*3, and that 3 is prime. So we can fully decompose 18 into 2*3*3.

For slightly larger numbers we may need a computer to try possible factors for us. Here is a simple PHP prime factorization function which will implements the simplest possible prime factorization algorithm – just trying all possible factors. It returns an array of prime factors.

function prime_factors($n) {

$f = array();

for($j=2;$j<=$n; $j++) {

while ($n/$j == floor($n/$j)) { $f[]=$j; $n/=$j; }

}

return $f;

}

For much larger numbers (with hundreds of digits) there is no easy way to recover the prime factorization of some numbers (a fact that is exploited in *cryptography*). Advanced prime factorization algorithms, such as *field* *sieves, *help make larger numbers factorizable but these are beyond the scope of this post.

Sometimes you might be asked to find the greatest or largest prime factor. This is simply the numerically largest of the prime factors we obtain by following the prime factor decomposition described above. So in the example where we found that 52=2*2*13, the greatest prime factor of 52 is 13.

If you would like help with how to find the prime factorization of a number, or have any other questions about prime factorization, please feel free to ask a question in the Calcatraz math Q&A section.

Here are some questions with prime factorization examples:

You may also like to try out the calculator soup prime factor tool. It is a handy tool which shows both the prime factor tree and

If you’re a teacher, you may find the math-aids.com prime factorization worksheet generator useful. It lets you generate prime factorization worksheets with question sheets for your students, and answer sheets for you.

If you’re a student, you may find the prime factorization games by Mr Nussbaum useful.

Here is a table giving the prime factors of the first 100 numbers:

Composite | Prime Factorization |
---|---|

2 | 2 |

3 | 3 |

4 | 2×2 |

5 | 5 |

6 | 2×3 |

7 | 7 |

8 | 2×2×2 |

9 | 3×3 |

10 | 2×5 |

11 | 11 |

12 | 2×2×3 |

13 | 13 |

14 | 2×7 |

15 | 3×5 |

16 | 2×2×2×2 |

17 | 17 |

18 | 2×3×3 |

19 | 19 |

20 | 2×2×5 |

21 | 3×7 |

22 | 2×11 |

23 | 23 |

24 | 2×2×2×3 |

25 | 5×5 |

26 | 2×13 |

27 | 3×3×3 |

28 | 2×2×7 |

29 | 29 |

30 | 2×3×5 |

31 | 31 |

32 | 2×2×2×2×2 |

33 | 3×11 |

34 | 2×17 |

35 | 5×7 |

36 | 2×2×3×3 |

37 | 37 |

38 | 2×19 |

39 | 3×13 |

40 | 2×2×2×5 |

41 | 41 |

42 | 2×3×7 |

43 | 43 |

44 | 2×2×11 |

45 | 3×3×5 |

46 | 2×23 |

47 | 47 |

48 | 2×2×2×2×3 |

49 | 7×7 |

50 | 2×5×5 |

51 | 3×17 |

52 | 2×2×13 |

53 | 53 |

54 | 2×3×3×3 |

55 | 5×11 |

56 | 2×2×2×7 |

57 | 3×19 |

58 | 2×29 |

59 | 59 |

60 | 2×2×3×5 |

61 | 61 |

62 | 2×31 |

63 | 3×3×7 |

64 | 2×2×2×2×2×2 |

65 | 5×13 |

66 | 2×3×11 |

67 | 67 |

68 | 2×2×17 |

69 | 3×23 |

70 | 2×5×7 |

71 | 71 |

72 | 2×2×2×3×3 |

73 | 73 |

74 | 2×37 |

75 | 3×5×5 |

76 | 2×2×19 |

77 | 7×11 |

78 | 2×3×13 |

79 | 79 |

80 | 2×2×2×2×5 |

81 | 3×3×3×3 |

82 | 2×41 |

83 | 83 |

84 | 2×2×3×7 |

85 | 5×17 |

86 | 2×43 |

87 | 3×29 |

88 | 2×2×2×11 |

89 | 89 |

90 | 2×3×3×5 |

91 | 7×13 |

92 | 2×2×23 |

93 | 3×31 |

94 | 2×47 |

95 | 5×19 |

96 | 2×2×2×2×2×3 |

97 | 97 |

98 | 2×7×7 |

99 | 3×3×11 |

100 | 2×2×5×5 |

## Let's Discuss...