Make your own free website on
  Prime Factorization


About Us
C Programs


All composite numbers can be factored out into its prime roots. This is called prime factorization. There are several ways of doing this, as shown below.

The Factor Tree

This is the most common method of prime factorization, done by repetitively extracting prime-numbered factors from the given number until all the roots are prime.

For example, the number 162 can be factored as shown below:

Continuous Division by Prime Numbers

This method is quite similar to the factor tree in such a way that the principle used in factorization is the same. The only difference is that you divide the given number until you reach 1. Here is the way it is illustrated:

Fermat's Prime Factorization Method

Perhaps this is the most technical of all the methods given in this discussion. Yet it is the most algebraically based. Discovered by Pierre Fermat, this process is composed of three major steps:

  1. Get the smallest integer (represented by n) greater than the square root of the given number (let the given number be x).

  2. Find a number m equal to or higher than n in such a way that m2 - x would produce a perfect square value. If the difference is not a perfect square, try another number. Let this number be t.

  3. Let s be the square root of t. Arrange the numbers in the form m2 - s2 = x. Factor out the left side and you will arrive at two prime factors.

Here is an example:

x = 667

The square root of 667 is 25.8263, which is 26 when rounded off.

  • Let m = n = 26.

The square of 26 is 676. Thus, m2 - x = 676 - 667 = 9.

  • Let t = 9 and s = 3.

In the form m2 - s2 = x, the equation would be:

262 - 32 = 667

(26-3) (26+3) = 667

(23) (29) = 667

Thus you would get two values that is almost impossible to get using the previous two methods (unless you are a mathematician): 23 and 29.


Home | Determining Prime Numbers | Prime Factorization | Getting the Number of Divisors | The Sum and Product of Divisors


Copyright 2006. All rights reserved.

No part of this site may be reproduced without the permission of the authors.