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