Top

Prime Factorization Tree

  • An integer is a factor of another number if it divides the other number with remainder zero.
  • A prime number is an integer which has only two factors, 1 and itself.
  • A composite number is an integer which has more than two factors.
  • A prime factor of a number is a prime number which divides the number with 0 remainder.

What is prime factorization

Back to Top
A composite number written as a product of prime numbers is called the prime factorization of the number.
While writing the product, the order of the numbers does not matter due to the commutative property of multiplication. Hence there is only one prime factorization possible.

Example: The prime factorization of the number 60 is
60 = 2 x 2 x 3 x 5.

This can be equivalently written with exponents as,

60 = 22 x 3 x 5

The prime factorization is done using divisibility tests or trial divisions.The prime factors so found can also be shown as a factor tree which gives a visual description of the process used.

Prime factorization factor tree.

Back to Top
In the factor tree display of prime factorization, each level of division is shown as two branches.  One branch shows the prime number which divides the number and the other branch leads to the quotient obtained on division. The division and branching process is continued till a quotient obtained is a prime number.

Example:
Use a factor tree to find the prime factorization of 240.
The ones digit in 240 is 0.  This means the number is divisible by 10 and hence by also the factors of 10 which are 2 and 5. Dividing the number 240 by the smaller of the prime factors 2, the first branching is as follows:

                                                                                         240
                                                                                           /\
                                                                                          /  \
                                                              Prime factor  →    120
The quotient on division is 120. This again is divisible by 2. Continuing the factoring, dividing and branching  we get the prime factorization tree as follows:

                                                                                         240
                                                                                           /\
                                                                                          /  \
                                                              Prime factor  →    120
                                                                                               /\
                                                                                              /   \
                                                              Prime factor   →       60
                                                                                                   /\
                                                                                                  /  \
                                                              Prime factor  →          30
                                                                                                      /\
                                                                                                     /  \
                                                              Prime factor  →             15
                                                                                                         /\
                                                                                                        /  \
                                                              Prime factor  →                3    5   ←  Prime factor

We stop when we get the quotient the 5, which is a prime number. Hence the prime factorization of 240 is
240 = 2 x 2 x 2 x 2 x 2 x 3 x 5          or using exponents    240 = 24 x 3 x 5