Algorithm to find all factors of very large number

0 / 219
All factorization algorithm

 

Introduction and overview

 

 

Given a very large number, find all it’s factors using an efficient algorithm.

 

In continuation to our previous blog, we will see how the prime factorization algorithm can be extended to compute all factors of very large numbers.

 

To understand how the prime factorization algorithm works, refer our previous blog.

 

Once we compute the prime factors, finding all factors is simple using the below approach:-

 

  • Find prime factors of the number and create a map of prime divisors and it’s frequencies (JSON object with key as prime divisor and value as it’s frequency)

 

  • Iterate through the list of prime divisors of the number and first push them in the list of final output of all factors array. 

 

  • Use recursion to find combinations of different factors by multiplying a bunch of prime divisors accounting their frequencies obtained in the JSON array in step 1. Keep pushing the multiplied results obtained in each iteration in the output array which will hold all factors of number.

 

  • Repeat step 2 until all prime divisor combinations are processed and all multiplication results are obtained. Once all prime divisors are processed, return the output array, referred in previous step which will have the intended result.

 

 

 

Below is a javascript code for the above algorithm:

 

<html>
</html>

<script>

// first we find all prime factors and using the prime factors, determine all non prime factors
window.onload = init;

function init() {
	var allFactors = solution(1e+21);
	
	console.log(allFactors);
}


// algorithm to calculate all Factors of very large number
function solution(N) {
	var output = [];
	findPrimeFactors(N, output);

	var uniquesObj = countUniques(output);
	var arr1 = [],
		arr2 = [],
		result = [];

	for (var key in uniquesObj) {
		arr1.push((key));
		arr2.push(uniquesObj[key]);
	}
	
	findFactors(arr1, arr2, 0, 1, result );

	return (N === 0 || N ===1) ? [N] : result.sort((a,b) => a-b);
}

// count frequencies of all prime divisors and return json object with prime divisor as key and it's frequency as value
function countUniques(arr) {
	return arr.reduce((prev, curr) => (prev[curr] = ++prev[curr] || 1, prev), {})
}

function findFactors(primeDivisors, multiplicity, currentDivisor, currentResult, output) {
	if (currentDivisor == primeDivisors.length) {
		output.push(currentResult);
		return;
	}

	for (var i = 0; i <= multiplicity[currentDivisor]; ++i) {
		findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult, output);
		currentResult *= primeDivisors[currentDivisor];
	}
}

// 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)) {
		factors.push(num);
		return factors;
	}
	// check if number if even
	if (num % 2 === 0) {
		// check if number is even and push even factor in output array
		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) {
			factors.push(j);
		}
		findPrimeFactors(parseInt(num / j), factors); // recursive call. Continue until all prime factors are found
	}
}

</script>

 

Note:- Javascript rounds of numbers with higher than 15 digits, so results may be incorrect. To get around that problem, use a third party library like BigInteger or something similar.

 

 

C++ is more efficient and fast and has better precision. Below is the same JS code translated to C++

 

 

#include <bits/stdc++.h> 
using namespace std; 
  
  
// checks if the given number is prime
long long isPrime(long long number, int getIndex = -1) {
	for (long long t = 2; t <= round(sqrt(number)); t++) {
		if (number % t == 0) {
			if (getIndex != -1) return t;
			return -1;
		}
	}

	return -2;
}

// A function to print all prime  
// factors of a given number n  
void findPrimeFactors(long long num, vector <long long int> &factors)  
{  
	if (isPrime(num) == -2) {
		factors.push_back(num);
		return;
	}
	// check if number if even
	if (num % 2 == 0) {
		// check if number is even and push even factor in output array
		factors.push_back(2);
		findPrimeFactors(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
		long long j = isPrime(num, -2);
		if (j >= 2) {
			factors.push_back(j);
		}
		findPrimeFactors(num / j, factors); // recursive call. Continue until all prime factors are found
	}
}  



void findAllFactors(vector <long long> primeDivisors, 
vector <int> multiplicity, 
long long currentDivisor, 
long long currentResult, 
vector <long long> &output) {
	if (currentDivisor == primeDivisors.size()) {
		output.push_back(currentResult);
		return;
	}

	for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
		findAllFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult, output);
		currentResult *= primeDivisors[currentDivisor];
	}
}
  
/* Driver code */
int main()  
{  
    long long n = 630407967398130281; 
	vector <long long> factors;
	vector <long long> allFactors;
    findPrimeFactors(n, factors);
    
    // Mark all array elements as not visited 
    vector<bool> visited(factors.size(), false);
    vector<long long> arr1;
    vector<int> arr2;
  
    // Traverse through array elements and 
    // count frequencies 
    for (int i = 0; i < factors.size(); i++) { 
  
        // Skip this element if already processed 
        if (visited[i] == true) 
            continue; 
  
        // Count frequency 
        int count = 1; 
        for (int j = i + 1; j < factors.size(); j++) { 
            if (factors[i] == factors[j]) { 
                visited[j] = true; 
                count++; 
            } 
        } 
        // cout << factors[i] << " " << count << endl;
        arr1.push_back(factors[i]);
        arr2.push_back(count);
    }
    
    findAllFactors(arr1, arr2, 0, 1, allFactors);
    
     cout << "All factors of " << n << " are:- "<< endl;
	
	for (vector<long long>::iterator it = allFactors.begin(); it != allFactors.end(); ++it) 
        cout << " " << *it;
        
        
    return 0;  
}

 

 

Demo :- http://code.golibrary.co/pDmoODJKYvRw

 

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