# How to do prime factorization

Prime factorization is a way of expressing a number as a product of prime numbers. The prime numbers used in the product statement are called the prime factors of the number.
Example:
24 = 2 x 2 x 2 x 3.  This statement is the prime factorization for the number 24. The numbers 2 and 3 are the prime factors of 24.

## Methods for prime factorization

1. Divisibility test
If a number is a factor of the another number, then the first number divides the second number leaving no remainder. This property of factors is used in determining the prime factors of a number. The given number is repeatedly and progressively tested for divisibility by prime numbers starting from 2 till the final quotient is a prime. Then all the divisors along with the final quotient are written as a prime  factorization for the given number.

Example:

Prime factorization of 72 = 2 x 2 x 2 x 3 x 3

2. Prime factorization trees
Prime factorization trees indeed demonstrates the process of repeated and progressive division explained above.
Prime factorization trees are commonly known as factor trees. The factor tree for 72 can be shown as follows:

72
/\
/  \
36
/\
/  \
18
/\
/  \
2   9
/\
/  \

3  3

## How to do prime factorization trees?

Let us do the prime factorization tree for the composite number 90.  The digit in ones place is 0.  This means the number is divisible by 10 and hence 2 and 5 are factors of 90. Dividing 90 by the smaller prime number 2, we get the quotient as 45.  That means 2 and 45 are the factors of 90.  These numbers can be shown branching out of 90 as follows:

90
/\
/  \
Prime factor  →      45
Now the sum of the digits of the number 45  = 4+5 =9 which is divisible by 3. Hence 45 is divisible by 3.Dividing 45 by 3 leaves a quotient 15. Hence the branching can be continued as follows:

90
/\
/  \
Prime factor  →    45
/\
/  \
Prime factor  →     15
Final;y 15 can be factored as 3 x 5 and the factor tree can be completed.

90
/\
/  \
Prime factor  →  45
/\
/  \
Prime factor  →     15
/\
/  \
Prime factor  →    3   5  ←  Prime factor

The prime factorization displayed by tree is 90 = 2 x 3 x 3 x 5