Ask Dr. Math

Finding Prime Factors

Prime Factoring

Factoring is an idea you might be familiar with from multiplication. Numbers that can be multiplied together to get another number are its factors. For example, 4*3 = 12, so 3 and 4 are factors of 12. However, they're not its only factors; 1, 2, 6, and 12 are other factors of 12. (Another way of defining a factor is a number that goes evenly into the number you're factoring.)

A number is prime if it can not be divided evenly by anything except itself and 1. For example, 5 is a prime number, because the only factors of 5 are 1 * 5 = 5. However, 12 is not a prime number, because 1 * 12 = 12, 2 * 6 = 12, and 3 * 4 = 12. Prime factorization means finding all the prime numbers that are factors of a number.

It's helpful to have in your head the divisibility rules for prime numbers like 2, 3, 5, and 7. You'll find them in the Dr. Math FAQ:

Divisibility Rules

   2  If the last digit is even, the number is divisible by 2.
   3  If the sum of the digits is divisible by 3, the number 
      is also.
   4  If the last two digits form a number divisible by 4, 
      the number is also. 
   5  If the last digit is a 5 or a 0, the number is divisible 
      by 5. 
   6  If the number is divisible by both 3 and 2, it is also 
      divisible by 6. 
   7  Take the last digit, double it, and subtract it from the 
      rest of the number; if the answer is divisible by 7 
      (including 0), then the number is also. 
   8  If the last three digits form a number divisible by 8, 
      then the whole number is also divisible by 8. 
   9  If the sum of the digits is divisible by 9, the number 
      is also. 
  10  If the number ends in 0, it is divisible by 10.

A good basic knowledge of the multiplication table is also a help, together with familiarity with smaller prime numbers (2,3,5,7,11,13,17,19).

Let's take an example. How would you find the prime factorization of 126? Well, one way you could start would be by noticing that 126 is even. 2 is the only even prime number, and it divides evenly into every even number. So, if we divide 126 by 2 we get 63.

    126 = 2 x 63

Next we know from our multiplication tables that 63 = 7 x 9.

    126 = 2 x 7 x 9

We know that 7 is prime; what about 9? Nine is not prime: 9 = 3 x 3.

    126 = 2 x 7 x 3 x 3

Now we can stop since we have reached only prime numbers. The prime factors of 126 are: 2 x 3 x 3 x 7, or 2 x 3^2 x 7.