* Site-Outage Notice: Our engineering elves will be tweaking the Shmoop site from Monday, December 22 10:00 PM PST to Tuesday, December 23 5:00 AM PST. The site will be unavailable during this time.
Dismiss

# Prime Factorization

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

Samples:

1 is not prime
2 is prime
3 is prime
4 is not prime because 4 is divisible by 2

2 is the only even number that is prime. Whoop-dee-doo for number 2. For any other even number n, 2 divides n, so n is not prime.

Click here to see a list of the first 1,000 primes (http://primes.utm.edu/lists/small/1000.txt). 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 1,000 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.

Sample: 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 2 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 example.

Sample: Find the prime factorization of 120.

120 is divisible by 2, so "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.

60 is divisible by 2, so "pull out" 2 from 60: 120 = 2 × 2 × 30
30 is divisible by 2: 120 = 2 × 2 × 2 × 15
15 = 3 × 5, and 3 and 5 are both prime numbers.
So: 120 = 2 × 2 × 2 × 3 × 5.

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