Integer factorization is a process of decomposition of a number into a product of its prime divisors. It is believed that the process of factorization is from the computational point of view very complex, hence it is used in many cryptosystems (e.g. RSA). Prime factorization may be also used to find the least common multiple or the greatest common divisor of two integers.

Examples

15 = 3 \\cdot 5
105 = 3 \\cdot 5 \\cdot 7
525 = 3 \\cdot 5 \\cdot 5 \\cdot 7
1025 = 5 \\cdot 5 \\cdot 41
4352= 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 17

Complexity of integer factorization

The complexity of integer factorization is often left unclear. If we look at the classical implementation of the factorization, which iteratively tries to divide a number with all number less or equal to its square root, one may think that the complexity is polynomial (square root of n). However this conclusion is not correct.

The complexity of algorithm is defined as a function of the length of the input, not its numerical value. The twice as big input has two times more digits. Because the input is in the n-ary (binary, octal decimal...) numeral system, the numerical value is growing exponentially. Hence the complexity of the algorithm in respect to the length of the input is exponential.


Code

01./**
02. * Factorizes the number n (prints out x1 x2 ... xn, where xi is a prime factor of n)
03. * @param number number to be factorized
04. */
05.public static void factorize(int number) {
06. 
07.    int remainder = number;
08.    for (int i = 2; i <= Math.sqrt(remainder); i++) {
09.         
10.        // For all i less or equal to sqrt(remainder)
11.        //  try to factorize the remainder
12.        while (remainder % i == 0) {
13.            remainder = remainder / i;
14.            System.out.print(i + " ");
15.        }
16.    }
17.    // If the remainder is greater than 1, than it must be a prime
18.    //  otherwise it would be already decomposed
19.    if (remainder > 1) {
20.        System.out.print(remainder);
21.    }
22.}
01./**
02. * Factorizes the number n (prints out x1 x2 ... xn, where xi is a prime factor of n)
03. * @param number number to be factorized
04. */
05.void factorize(int number) {
06. 
07.    int remainder = number;
08.    for (int i = 2; i <= sqrt(remainder); i++) {
09.         
10.        // For all i less or equal to sqrt(remainder)
11.        //  try to factorize the remainder
12.        while (remainder % i == 0) {
13.            remainder = remainder / i;
14.            cout << i << " ";
15.        }
16.    }
17.    // If the remainder is greater than 1, than it must be a prime
18.    //  otherwise it would have been already decomposed
19.    if (remainder > 1) {
20.        cout << remainder;
21.    }
22.}
01./**
02. * Factorizes the number n (prints out x1 x2 ... xn, where xi is a prime factor of n)
03. * @param $number number to be factorized
04. */
05.function factorize($number) {
06. 
07.    $remainder = $number;
08.    for ($i = 2; $i <= sqrt($remainder); $i++) {
09.         
10.        // For all i less or equal to sqrt(remainder)
11.        //  try to factorize the remainder
12.        while ($remainder % $i == 0) {
13.            $remainder = $remainder / $i;
14.            echo $i . " ";
15.        }
16.    }
17.    // If the remainder is greater than 1, than it must be a prime
18.    //  otherwise it would have been already decomposed
19.    if ($remainder > 1) {
20.        echo $remainder;
21.    }
22.}







       
 

Place for your banner

Here is the position ready for our customer's banners.