## Algorithm to find all factors of very large number

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