Prime Factorization
How to write an efficient algorithm to find prime factors of very large numbers ?
Below is a simple algorithm to achieve the same:-
- Check if the given number is prime, if true, push it to an output array of factors
- Check if number is even, if yes, push 2 as one of it's factors in the output array and fire a recursive call to check for factors of Integer(num / 2)
- If step 2 is false i.e, number is either prime or odd. Find further factors of the number and push it in the output array of factors.
- Make a recursive call to the function by passing num/<factor obtained in step 3>
- When base condition is met, i.e the final number is prime and can't be further factored, exit the loop and return the output array of factors.
- As some factors could be duplicated, we maintain a JSON map to check if it already exists in it. If not, only then we push it to the array of output prime factors.
Below is the recursive solution to this using javascript
<html> </html><script>
var map = {};
init();
function init() {
var n = 720720, output = [];findPrimeFactors(n, output);
document.write('Prime factors of '+n+' are: '+output);
}// checks if the given number is prime
function isPrime(number, getIndex = false) {
for (var t = 2; t <= Math.round(Math.sqrt(number)); t++) {
if (number % t === 0) {
if (getIndex) return t;
return false;
}
}return true;
}// find prime factors of given number. Returns an array of prime factors of number
function findPrimeFactors(num, factors = []) {
if (isPrime(num)) {
if (typeof map[num] === 'undefined') {
factors.push(num);
map[num] = num;
}return factors;
}// check if number if even
if (num % 2 === 0) {
// check if number is even and push even factor in output array
if (typeof map[2] === 'undefined') {
map[2] = 2;
factors.push(2);
}findPrimeFactors(parseInt(num / 2), factors);// recursive call. Continue until all prime factors are found
} else {
// check if number is odd or prime and push prime/odd factor in output array
var j = isPrime(num, true);
if ( j >= 2) {
if (typeof map[j] === 'undefined') {
map[j] = j;
factors.push(j);
}
}
findPrimeFactors(parseInt(num/j), factors);// recursive call. Continue until all prime factors are found
}
}</script>
Try the above code on our code playground at http://code.golibrary.co
Below is the code using iterative approach
function primeFactors(n, output=[]) { console.log('here is ', n, n % 2); // Print the number of 2s that divide n while (n % 2 === 0) { document.write('2 '); n = parseInt(n/2); }// n must be odd at this point. So we can skip // one element (Note i = i +2) for (var i = 3; i <= parseInt(Math.sqrt(n)); i = i + 2) { // While i divides n, print i and divide n while (n % i == 0) { document.write(i+" "); n = parseInt(n/i); } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) document.write(n+" ");}
Note:- Javascript rounds of integers if they are more than 15 digits. So the above code may not work unless you try it using some third party library like BigInteger.
Stay tuned to our next article. We will extend this algorithm to find all factors of very big numbers.
Demo here:- http://code.golibrary.co/o3dVOqoBYAQR
Subscribe and follow Golibrary on Facebook and Linkedin to get all the updates.
Posted from my blog with SteemPress : https://www.golibrary.co/algorithm-to-find-prime-factors-of-very-big-numbers/