Check if a number is Prime or not

In this tutorial let us look at different methods to check if a number is prime or not in JavaScript and understand where exactly are these useful. A prime number is a natural number greater than 1 that cannot be obtained by multiplying two smaller natural numbers. All the other non prime natural numbers greater than 1 are called composite numbers.

Examples of Prime numbers: 2,3,5,7,11,13 etc.
Examples of Composite numbers: 4,6,8,9,10,12,14 etc.

Table of Contents


Where are prime numbers used in real life?

Prime numbers are used widely in cryptography and in-turn in encryption. Check out this article to get a clear understanding. Prime numbers are also used in computer-generated pseudo-random numbers.

Code

Version 1

This version is very slow and but has the least number of lines of code. It checks if n is divisible by every integer up to square root of the passed value . Before doing this it checks whether a value is NaN or not. NaN values are generated when arithmetic operations result in undefined or unpresentable values. The isNaN() function is used for this. It also checks if the value passed is finite or not by using the isFinite() function.

//isPrime Javascript Version 1
function isPrime1(n) {
 if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false;
 var m=Math.sqrt(n); //returns the square root of the passed value
 for (var i=2;i<=m;i++) if (n%i==0) return false;
 return true;
}

console.log(isPrime1(7)); //Output: True
console.log(isPrime1(6)); //Output: False


Version 2

This version relatively better than the first one. It first checks if the passed value is an even number or not. After this it proceeds to check odd divisors only, from 3 up to square root of the passed value. At most half of the numbers between 3 and square root of the passed value are checked.

//isPrime Javascript Version 2
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;
}

console.log(isPrime2(7)); //Output: True
console.log(isPrime2(6)); //Output: False


Version 3

This version is even better. The following checks are performed in addition to the previous versions before checking the rest of the devisors in the loop.
  • Check 1: If n is divisible by 2 or 3.
  • Check 2: Check only the odd divisors that are not multiples of 3.
In this version, at least two thirds of divisors up to square root of n are eliminated(i.e. All the multiples of 2 & 3 are eliminated)

//isPrime Javascript Version 3
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;
}

console.log(isPrime3(7)); //Output: True
console.log(isPrime3(6)); //Output: False


Version 4

This is the fastest of all the versions. In addition to 2 and 3, multiples of 5 are also eliminated in the loop. The result of this would be that we end up checking at max quarter numbers between 2 and the square root of n.

//isPrime Javascript Version 4
isPrime = function(n) {
 if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false;
 if (n==leastFactor(n)) return true;
 return false;
}

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;
}

console.log(isPrime(7)); //Output: True
console.log(isPrime(6)); //Output: False