Prime Factorization

Prime Factorization is a further restricted version of integer factorization wherein we are trying to factor our given number down to prime numbers.

Let's look at an example. For this example let's see what the prime factors of 12 are. It is best to start working from the smallest prime number, which in this case is 2: 12 / 2 = 6. Being that 6 is not a prime number we would then see if we can go further: 6 / 2 = 3. Since 3 is a prime number our prime number factorization would look like: 12 = 2 x 2 x 3 or 12 = 2^2 x 3.

Now let's look at a slightly more involved example. Let's see what the prime factorization of 147 is. Since 147 is an odd number we know that we can't divide by 2, but since the digits of 147 add up to a number that is divisible by 3 we know that we can divide by 3: 1 + 4 + 7 = 12. That is a little trick you can do to see if a number is divisible by 3 without having to bust out a calculator. So let's divide by 3: 147 / 3 = 49. Again since 49 is not a prime number we shall try to factor that: 49 / 7 = 7. That means the prime factorization of 147 is: 147 = 3 * 7^2.

Prime factorization is a good concept to at least understand as it makes up the backbone of cryptography.