Algorithm to find all factors of very large number
0
/
472
- 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.
<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>
#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;
}
Comments
