# Prime Factorization

A prime number is a number greater than 1 that's only divisible by itself and 1. It's like someone fed it into a factor compactor.

Here are some examples:

1 is not prime.
2 is prime.
3 is prime.
4 is not prime because it's divisible by 2.
5 is prime.
6 is not prime because it's divisible by 2 and 3.

As it turns out, 2 is the only even number that's prime. Whoop-dee-doo for number 2. For any other even number n, 2 divides into n, so n is not prime.

Click here to see a list of the first 1000 primes. It's good to be able to recognize the prime numbers at least up to 31 or so. However, if you want to memorize all 1000 of them, we won't stop you. Having the ability to rattle them off will be a great party trick, if nothing else. By the way, how do you get invited to such cool parties?

Every single whole number can be written uniquely (in only one way) as a product of primes.

For example, 12 breaks down like this:

12 = 2 × 2 × 3

We can reorder the product and write 12 = 2 × 3 × 2, or 12 = 3 × 2 × 2, but we can't write 12 as a product using any other prime numbers. We have to use two copies of 2 and one copy of 3. It's the law.

To find the prime factorization of a number, you can "pull out" one prime at a time. Put your back into it.

We'll illustrate what this means by an example, mostly because we're terrible at drawing stuff.

### Sample Problem

Find the prime factorization of 120.

Okay, 120 is divisible by 2, so first we "pull out" a 2:

120 = 2 × 60

Always look first to see if you can pull out a 2. That's always our "prime suspect." Oh, sure, groan away.

Now we move on to the 60. Since 60 is also divisible by 2, we "pull out" 2 from 60:

120 = 2 × 2 × 30

Ah, but 30 is also divisible by 2:

120 = 2 × 2 × 2 × 15

So far, so good. We can't divide that 15 by 2, but we can divide it by 3 because 15 = 3 × 5, and 3 and 5 are both prime numbers.

120 = 2 × 2 × 2 × 3 × 5

We've reached the end at last. All those factors are now prime numbers, so we can't split 120 up any further.

Another way to find the prime factorization of a number is to simply recognize the number as a product of two smaller numbers, and factor each of the smaller numbers. Better recognize.

### Sample Problem

What's the prime factorization of 200?

200 = 20 × 10
= (4 × 5) × (2 × 5)
= (2 × 2 × 5) × (2 × 5)
= 2 × 2 × 2 × 5 × 5

Since there's only one way to write any particular number as a product of primes, it doesn't matter what method you use to find those primes. There are certain methods that are slower, such as counting out that number of pennies and then dividing them into neat, even piles, but you'll still arrive at the correct answer eventually. Now get yourself to a Coinstar, you penny hoarder.