## Algorithm to find prime factors of very big numbers

**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.

**CPP performs slightly better as it shows proper warnings and has better precision when it comes to handling large numbers**.

**Below is a small code in C++ to find prime factors:**

#include <bits/stdc++.h> using namespace std; // A function to print all prime // factors of a given number n vector <long long > primeFactors(long long n, vector <long long int> &factors) { // Print the number of 2s that divide n while (n % 2 == 0) { factors.push_back(2); n = n/2; } // n must be odd at this point. So we can skip // one element (Note i = i +2) for (long long i = 3; i <= sqrt(n); i = i + 2) { // While i divides n, print i and divide n while (n % i == 0) { factors.push_back(i); n = n/i; } } // This condition is to handle the case when n // is a prime number greater than 2 if (n > 2) factors.push_back(n); return factors; } /* Driver code */ int main() { long long n = 630407967398130281; vector<long long int> factors; primeFactors(n, factors); for (vector<long long>::iterator it = factors.begin(); it != factors.end(); ++it) cout << " " << *it; return 0; }

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.*