Prime factorization of a number is the process if writing a number as a product of prime numbers. A Prime factorization algorithm is expected to list the general steps involved in finding the prime factorization of a number. A software program written based on such algorithm can thus be used by computer systems to determine the prime factorization of large numbers quickly.

## Difficulty in writing a general algorithm

Hence an efficient algorithm can be written only by making use of some additional information about the number whose prime factorization is to be written.

## Simplest algorithm to find the prime factorization.

- Test the divisibility of the number with the smallest prime number 2.
- If it is divisible by 2, then write the number as a product of 2 and the quotient obtained on division. If it is not divisible by 2 then step 4.
- If the quotient is divisible by 2 continue division. Continue division till you get a quotient which is not divisible by 2.
- Try doing the trials described in steps 1 to 3 for the next prime number.
- Stop the trials when the quotient obtained in a trial process is a prime number.

1. 3768 is an even number. Hence it is divisible by 2.

2. On division by 2 we get the quotient as 1884. Hence the first factored form is

**3768 = 2 x 1884**

3. The quotient got in step 2 is again divisible by 2 and we get a quotient of 942 on dividing 1884 by 2.

**3768 = 2 x 2 x 942**

One more division with 2 is possible we get the factored form as

**3768 = 2 x 2 x 2 x 471**

4. We need to test the divisibility of 471 with 3. Since the sum of the digits 4 + 7 + 1 =12 is divisible by 3, the number is divisible by 3.

And the factored form now becomes

**3768 = 2 x 2 x 2 x 3 x 157**

5. As 157 is a prime number, the division has to be stopped.

Hence the prime factorization of 3768 is

**3768 = 2 x 2 x 2 x 3 x 157**or using exponents,

**157 = 2**

^{3}x 3 x 157