How to write an efficient algorithm to find prime factors of very large numbers ?
Below is a simple algorithm to achieve the same:-
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.
