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 = 23 x 3 x 157