Primality Test in JavaScript:
isPrime(n) and leastFactor(n)
JavaScript FAQ |
JavaScript Numbers FAQ
|
Question: How do I test if a given number n is prime in JavaScript?
Answer:
JavaScript does not have a standard function to do this.
To check if n is prime, you would need to define your own function like the following (see source code below):
isPrime(n)
returns true if n is prime, and false otherwise
leastFactor(n)
returns the smallest prime that divides n (for integer n>1).
Click the Run button to display the results of the function calls
isPrime(n) and
leastFactor(n) and measure the execution time.
Here are several versions of the function isPrime(n).
All versions check the primality by trial division; so, all versions are, in a sense, brute force tests.
However, note that the version with the fewest lines of code takes the longest to run for a large prime n –
thus, not all brute force tests are created equal:
// This version has the fewest lines of code - but is very slow.
// It checks if n is dividible by every integer 2, 3, 4, 5 ...
// up to sqrt(n)
function isPrime1(n) {
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false;
var m=Math.sqrt(n);
for (var i=2;i<=m;i++) if (n%i==0) return false;
return true;
}
// The next version is better: it checks the divisor 2 separately;
// then, it proceeds to check odd divisors only, from 3 up to sqrt(n).
// At most half of the numbers between 3 and sqrt(n) are checked.
function isPrime2(n) {
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false;
if (n%2==0) return (n==2);
var m=Math.sqrt(n);
for (var i=3;i<=m;i+=2) {
if (n%i==0) return false;
}
return true;
}
// Even better: first, check if n is divisible by 2 or 3.
// Then check only the odd divisors that are not multiples of 3.
// At most 1/3 of divisors under sqrt(n) are checked;
// other divisors are multiples of either 2 or 3 anyway.
function isPrime3(n) {
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false;
if (n%2==0) return (n==2);
if (n%3==0) return (n==3);
var m=Math.sqrt(n);
for (var i=5;i<=m;i+=6) {
if (n%i==0) return false;
if (n%(i+2)==0) return false;
}
return true;
}
Below is the source code of the functions for primality testing that are actually used on this page.
This code works even faster than the fastest version listed above. Here only about a quarter of divisors
under sqrt(n) are checked in the main for loop; the other three-quarters
(multiples of 2, 3, or 5) are immediately eliminated in the initial checks, before entering the for loop:
isPrime = function(n) {
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false;
if (n==leastFactor(n)) return true;
return false;
}
// leastFactor(n)
// returns the smallest prime that divides n
// NaN if n is NaN or Infinity
// 0 if n=0
// 1 if n=1, n=-1, or n is not an integer
leastFactor = function(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;
}
If you look at the source code of primefactors.js,
you will notice additional browser-specific optimizations.
Want more information on primes and primality tests in JavaScript?
Please visit the JavaScripter.net Math section,
particularly these pages: