What is prime factorization?

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”.

What is a prime number?

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.

What is factorization?

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.

So, what is prime factorization?

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).

Find the prime factorization

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.

Greatest prime factor

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.

Help me find a prime factorization

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

Prime factorization activities / resources

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.

Prime factorization table

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

CompositePrime Factorization
22
33
42×2
55
62×3
77
82×2×2
93×3
102×5
1111
122×2×3
1313
142×7
153×5
162×2×2×2
1717
182×3×3
1919
202×2×5
213×7
222×11
2323
242×2×2×3
255×5
262×13
273×3×3
282×2×7
2929
302×3×5
3131
322×2×2×2×2
333×11
342×17
355×7
362×2×3×3
3737
382×19
393×13
402×2×2×5
4141
422×3×7
4343
442×2×11
453×3×5
462×23
4747
482×2×2×2×3
497×7
502×5×5
513×17
522×2×13
5353
542×3×3×3
555×11
562×2×2×7
573×19
582×29
5959
602×2×3×5
6161
622×31
633×3×7
642×2×2×2×2×2
655×13
662×3×11
6767
682×2×17
693×23
702×5×7
7171
722×2×2×3×3
7373
742×37
753×5×5
762×2×19
777×11
782×3×13
7979
802×2×2×2×5
813×3×3×3
822×41
8383
842×2×3×7
855×17
862×43
873×29
882×2×2×11
8989
902×3×3×5
917×13
922×2×23
933×31
942×47
955×19
962×2×2×2×2×3
9797
982×7×7
993×3×11
1002×2×5×5

Comments

Share your thoughts