Algorithm to find prime factors of very big numbers

0 / 158
primefactorization algorithm

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.

 

 

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts