Algorithm to find prime factors of very big numbers
0
/
461
- 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.
<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>
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 + " ");
}
#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;
}
Comments
