Factoring numbers below 2^53 in JavaScript
Doing math with JavaScript
Below is a recursive JavaScript function factor(n)
that returns the prime factorization of the input integer n.
It relies on the function leastFactor(n) to find the
least prime factor of n. The input number n must not exceed 253 = 9007199254740992.
(JavaScript variables cannot store odd numbers greater than 253,
so factoring integers greater than that requires additional tricks;
see e.g. Prime Factors Calculator.)
function factor(n) {
if (isNaN(n) || !isFinite(n) || n%1!=0 || n==0) return ''+n;
if (n<0) return '-'+factor(-n);
var minFactor = leastFactor(n);
if (n==minFactor) return ''+n;
return minFactor+'*'+factor(n/minFactor);
}
// find the least factor in n by trial division
function leastFactor(n) {
if (isNaN(n) || !isFinite(n)) return NaN;
if (n==0) return 0;
if (n%1 || n*n<2) return 1;
if (n%2==0) return 2;
if (n%3==0) return 3;
if (n%5==0) return 5;
var m = Math.sqrt(n);
for (var i=7;i<=m;i+=30) {
if (n%i==0) return i;
if (n%(i+4)==0) return i+4;
if (n%(i+6)==0) return i+6;
if (n%(i+10)==0) return i+10;
if (n%(i+12)==0) return i+12;
if (n%(i+16)==0) return i+16;
if (n%(i+22)==0) return i+22;
if (n%(i+24)==0) return i+24;
}
return n;
}
Click the Run button to measure the execution time of the function call in the left column.
(For more accurate results, use the average execution time over several runs.)