Prime factorization

Prime factorization is the expression of a composite (not prime) number as the product of its prime factors. Every composite number can be expressed with prime factors and has only one prime factorization.

How to find the prime factorization of a number

There are many different methods for finding the prime factorization of an integer. Below are two common methods used for smaller numbers. As the composite number becomes larger, it becomes more tedious and difficult to determine its prime factorization. For very large numbers, there is no known, efficient algorithm.


Trial division

Trial division is one of the methods used to find the prime factorization of a composite number. To use trial division:

  1. Divide the composite number by the smallest possible prime number that will divide it exactly (no remainder).
  2. If the quotient is not 1, divide the quotient again by the smallest prime number that will divide it exactly.
  3. Repeat step 2 until the quotient is 1.
  4. The prime factorization is the product of all the prime numbers used in division.

Example

Find the prime factorization of 102 using trial division.

102 ÷ 2 = 51

51 ÷ 2 = 25.5

25.5 is not a whole number so divide by the next smallest prime number.

51 ÷ 3 = 17

17 is a prime number, so it can only be formed as the product of 1 and 17.

17 ÷ 17 = 1

The quotient is 1, so the division process is complete. The prime factorization of 102 is the product of all the prime factors used in the division:

2 × 3 × 17 = 102


Factor tree

To find the prime factorization of a composite number using a factor tree:

  1. Write the composite number.
  2. Determine a pair of factors of the composite number, and draw two "branches" from it that terminate on opposite sides.
  3. Write the factors at the end of each branch.
  4. Repeat steps 2 and 3, using the number at the terminal end of each branch as the new base until the factors are prime factors.
  5. The product of all the prime factors is the prime factorization of the number.

Example

Find the prime factorization of 24.

24 can be formed by a few different pairs of factors, as shown above. Regardless which 2 factors are used at the beginning of the factor tree, the end result is the same. The prime factorization of 24:

2 × 2 × 2 × 3 = 24