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
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 ). 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
/**
* Factorizes the number n (prints out x1 x2 ... xn, where xi is a prime factor of n)
* @param number number to be factorized
*/
public static void factorize(int number) {
int remainder = number;
for (int i = 2; i <= Math.sqrt(remainder); i++) {
// For all i less or equal to sqrt(remainder)
// try to factorize the remainder
while (remainder % i == 0) {
remainder = remainder / i;
System.out.print(i + " ");
}
}
// If the remainder is greater than 1, than it must be a prime
// otherwise it would be already decomposed
if (remainder > 1) {
System.out.print(remainder);
}
}
/**
* Factorizes the number n (prints out x1 x2 ... xn, where xi is a prime factor of n)
* @param number number to be factorized
*/
void factorize(int number) {
int remainder = number;
for (int i = 2; i <= sqrt(remainder); i++) {
// For all i less or equal to sqrt(remainder)
// try to factorize the remainder
while (remainder % i == 0) {
remainder = remainder / i;
cout << i << " ";
}
}
// If the remainder is greater than 1, than it must be a prime
// otherwise it would have been already decomposed
if (remainder > 1) {
cout << remainder;
}
}
/**
* Factorizes the number n (prints out x1 x2 ... xn, where xi is a prime factor of n)
* @param $number number to be factorized
*/
function factorize($number) {
$remainder = $number;
for ($i = 2; $i <= sqrt($remainder); $i++) {
// For all i less or equal to sqrt(remainder)
// try to factorize the remainder
while ($remainder % $i == 0) {
$remainder = $remainder / $i;
echo $i . " ";
}
}
// If the remainder is greater than 1, than it must be a prime
// otherwise it would have been already decomposed
if ($remainder > 1) {
echo $remainder;
}
}