[javascript] Number prime test in JavaScript

I'm trying to complete the Codewars challenge that asks you to check if a number is a prime number. For whatever reason, my solution doesn't seem to work for the square of odd prime numbers (e.g. 9 returns true instead of false).

function isPrime(num) {

  if (num === 2) {
    return true;
  } else if (num > 1) {
    for (var i = 2; i < num; i++) {

      if (num % i !== 0) {
        return true;
      } else if (num === i * i) {
        return false
      } else {
        return false;
      }
    }
  } else {
    return false;
  }

}

console.log(isPrime(121));

P.s. I included that second else/if statement because I was trying to solve the problem.

Following code uses most efficient way of looping to check if a given number is prime.

function checkPrime(number){    
    if (number==2 || number==3) {
    return true
}
    if(number<2 ||number % 2===0){
        return false
    }
    else{
        for (let index = 3; index <= Math.sqrt(number); index=index+2) {
            if (number%index===0) {
                return false
            }        
        }
    }
    return true
}

1. First check rules out 2 and lesser numbers and all even numbers
2. Using Math.sqrt() to minimize the looping count
3. Incrementing loop counter by 2, skipping all even numbers, further reducing loop count by half

function isAPrimeNumber(num){
     var counter = 0;
     //loop will go k equals to $num
     for (k = 1; k <= num; k++) {
      //check if the num is divisible by itself and 1
      // `%` modulus gives the reminder of the value, so if it gives the reminder `0` then it is divisible by the value
       if (num % k == 0) {
         //increment counter value 1
         counter  = counter  + 1;
        }
    }
   //if the value of the `counter is 2` then it is a `prime number`
  //A prime number is exactly divisible by 2 times only (itself and 1)
   if (counter == 2) {
     return num + ' is a Prime Number';
   }else{
    return num + ' is nota Prime Number';
   }
 }

Now call isAPrimeNumber() function by passing a value.

var resp = isAPrimeNumber(5);
console.log(resp);

Output:

5 is a Prime Number

It looks like your first if statement within the first 'if' statement within the for loop. Since if num = 9 and i = 2, 9 % i !== 0 but 9 is not prime since on the next iteration where i = 3, 9 % i === 0.

Here would be my answer to that question.

var isPrime = function(n) {
  if(typeof n !== 'number' || n <= 1 || n % 1 !== 0){
    return false;
  }
  for(var i = 2; i <= Math.sqrt(n); i += 1){
    if(n % i === 0){
      return false;
    }
  }
  return true;
};

The first if statement catches the edge cases. The for loop then checks from 2 up to the square root of n because of the mathematical property where no number has both of its factors greater than the square root of that number.

Hope this helps!

This is a more reliable solution if you want to find n prime numbers.

function findPrime(n) {
      const primes = [];
      loop1:
      for (let j = 0; primes.length < n; j++) {
       loop2:
       for(let i = 2; i < j; i++){
        if(j % i === 0){
            continue loop1;
        }
      }
      if(j>1) primes.push(j);
      }
      console.log(primes);
    }
     
    findPrime(5);

i think the easiest way to get it and faster is

function isPrime(num) {
  for(var i = 2; i < Math.sqrt(num); i++) {
      if(num % i === 0){
          return false;
       } 
  return num > 1; 
  }
}

console.log(isPrime(9))

This answer is based on the answer by Ihor Sakaylyuk. But instead of checking for all numbers, I am checking only the odd numbers. Doing so I reduced the time complexity of the solution to O(sqrt(n)/2).

function isPrime(num) {_x000D_
 if (num > 2 && num % 2 === 0) return false;_x000D_
 for (var i = 3; i < Math.sqrt(num); i += 2) {_x000D_
  if (num % i === 0) return false;_x000D_
 }_x000D_
 return num > 1;_x000D_
}

One of the shortest version

isPrime=(n)=>[...Array(n-2)].map((_,i)=>i+2).filter(i=>n%i==0).length==0

you can use below code in javascript for checking number is prime or not. It will reduce no of iteration and get the result fast.

function testPrime(num) {
        var isPrime = true;
        if (num >= 2) {
            if(num == 2 || num == 3){
               isPrime = true;
            }
            else if (num % 2 == 0) {
                isPrime = false;
            }
            else {
                for (i = 3; i <= Math.floor(Math.sqrt(num)); i += 2) {
                    if (num % i == 0) {
                        isPrime = false;
                        break;
                    }
                }
            }
        }
        else {
            isPrime = false;
        }
        return isPrime;
    }

//testPrime(21) false

This is how I'd do it:

function isPrime(num) {
  if(num < 2) return false;
  if(num == 2) return true;
  for(var i = 2; i < num; i++) {
    if(num % i === 0) return false;
  }
  return true;
}

Cool version:

const isPrime = n => ![...Array(n).keys()].slice(2).map(i => !(n%i)).includes(true) && ![0,1].includes(n)

function isPrime(num) {
    var prime = num != 1;
    for(var i=2; i<num; i++) {
        if(num % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

DEMO

very simple

const isPrime = num => {
  for (var i = 2; i < num; i++) if (num % i == 0) return false;
  return num >= 2; 
}

@IhorSakaylyuk's answer can be improved further down to O(sqrt(n/2)) by skipping all of the even numbers except 2:

const isPrime = number => {
    if(num % 2 === 0 && number !== 2) return false
    for(let i = 3, s = Math.sqrt(num); i <= s; i += 2)
        if(num % i === 0) return false; 
    return num > 1;
}

You can also use the npm package pial.

A small suggestion here, why do you want to run the loop for whole n numbers?

If a number is prime it will have 2 factors (1 and number itself). If it's not a prime they will have 1, number itself and more, you need not run the loop till the number, may be you can consider running it till the square root of the number.

You can either do it by euler's prime logic. Check following snippet:

function isPrime(num) {
  var sqrtnum=Math.floor(Math.sqrt(num));
    var prime = num != 1;
    for(var i=2; i<sqrtnum+1; i++) { // sqrtnum+1
        if(num % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

Now the complexity is O(sqrt(n))

For more information Why do we check up to the square root of a prime number to determine if it is prime?

Hope it helps

Might be useful for some people: An implementation of the Miller Rabin primality test. Works for all positive integers less than Number.MAX_SAFE_INTEGER.

Try on JSFiddle: https://jsfiddle.net/4rxhas2o/

let unsafeToSquare = Math.floor(Math.sqrt(Number.MAX_SAFE_INTEGER))

function addMod(a, b, m) {
  // Returns (a + b) % m

  let sum = a + b

  let result = sum % m

  if (sum < Number.MAX_SAFE_INTEGER)
    return result

  let signature = ((a % 8) + (b % 8)) % 8

  let sumMod = sum % 8

  for (let i = -2; i <= 2; ++i) {
    if ((sumMod + i) % 8 === signature) {
      let ret = result + i

      if (ret > m)
        ret = (result - m) + i // prevent overflow

      return ret
    }
  }
}

function mulMod(a, b, m) {
  if (m === 0)
    return 0

  let prod = a * b

  if (prod < Number.MAX_SAFE_INTEGER)
    return prod % m

  let y = 0
  let result = a

  while (b > 1) {
    if (b % 2 === 0) {
      result = addMod(result, result, m)

      b /= 2
    } else {
      y = addMod(result, y, m)
      result = addMod(result, result, m)

      b = (b - 1) / 2
    }
  }

  return addMod(result, y, m)
}

function squareMod(b, m) {
  // Computes (b * b % m)

  return mulMod(b, b, m)
}

function expModLargeB(b, exponent, m) {
  let y = 1

  while (exponent > 1) {
    if (exponent % 2 === 0) {
      b = squareMod(b, m)

      exponent /= 2
    } else {
      y = mulMod(y, b, m)
      b = squareMod(b, m)

      exponent = (exponent - 1) / 2
    }
  }

  return mulMod(b, y, m)
}

function expMod(b, exponent, m) {
  if (exponent === 0)
    return 1

  if (b >= unsafeToSquare || m >= unsafeToSquare) {
    return expModLargeB(b, exponent, m)
  }

  let y = 1

  while (exponent > 1) {
    if (exponent % 2 === 0) {
      b *= b
      b %= m

      exponent /= 2
    } else {
      y *= b
      b *= b

      y %= m
      b %= m

      exponent = (exponent - 1) / 2
    }
  }

  return (b * y) % m
}

function _isPrimeTrialDivision(p) {
  let sqrtP = Math.ceil(Math.sqrt(p))

  for (let i = 23; i <= sqrtP + 1; i += 2) {
    if (p % i === 0)
      return false
  }

  return true
}

function _isProbablePrimeMillerRabin(p, base=2) {
  let pm1 = p - 1
  let pm1div = pm1
  let d, r = 0

  while (true) {
    if (pm1div % 2 === 0) {
      pm1div /= 2

      r++
    } else {
      d = pm1div
      break
    }
  }

  let x = expMod(base, d, p)

  if (x === 1 || x === pm1)
    return true

  for (let i = 0; i < r - 1; ++i) {
    x = squareMod(x, p)

    if (x === pm1)
      return true
  }

  return false
}

function _isPrimeLarge(p) {
  let bases

  if (p < 2047)
    bases = [2]
  else if (p < 1373653)
    bases = [2, 3]
  else if (p < 9080191)
    bases = [31, 73]
  else if (p < 25326001)
    bases = [2, 3, 5]
  else if (p < 3215031751)
    bases = [2, 3, 5, 7]
  else if (p < 4759123141)
    bases = [2, 7, 61]
  else if (p < 1122004669633)
    bases = [2, 13, 23, 1662803]
  else if (p < 2152302898747)
    bases = [2, 3, 5, 7, 11]
  else if (p < 3474749660383)
    bases = [2, 3, 5, 7, 11, 13]
  else if (p < 341550071728321)
    bases = [2, 3, 5, 7, 11, 13, 17]
  else
    bases = [2, 3, 5, 7, 11, 13, 17, 19, 23]


  return bases.every(base => _isProbablePrimeMillerRabin(p, base))
}

let smallPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223]

function isPrime(p) {
  if (!Number.isInteger(p) || p < 2)
    return false

  // Test for small primes
  for (let i = 0; i < smallPrimes.length; ++i) {
    let prime = smallPrimes[i]

    if (p === prime)
      return true
    if (p % prime === 0)
      return false
  }

  if (p < 150) {
    return _isPrimeTrialDivision(p)
  } else {
    return _isPrimeLarge(p)
  }
}


const tests = [1, 2, 3, 10, 100, 100019, 10000000019, 100000000003, 10000000000037]
let start = performance.now()

tests.forEach(test => {
    console.log(`${test} is ${ isPrime(test) ? "" : "not " }prime`)
})

let end = performance.now()
console.log("Tests completed in " + (end - start) + " ms.")

You can try this one

function isPrime(num){_x000D_
    _x000D_
    // Less than or equal to 1 are not prime_x000D_
    if (num<=1) return false;_x000D_
    _x000D_
    // 2 and 3 are prime, so no calculations_x000D_
    if (num==2 || num==3 ) return true; _x000D_
    _x000D_
    // If mod with square root is zero then its not prime _x000D_
    if (num % Math.sqrt(num)==0 ) return false;_x000D_
    _x000D_
    // Run loop till square root_x000D_
    for(let i = 2, sqrt = Math.sqrt(num); i <= sqrt; i++) {_x000D_
    _x000D_
        // If mod is zero then its not prime_x000D_
        if(num % i === 0) return false; _x000D_
    }_x000D_
    _x000D_
    // Otherwise the number is prime_x000D_
    return true;_x000D_
   }_x000D_
   _x000D_
   _x000D_
   for(let i=-2; i <= 35; i++) { _x000D_
    console.log(`${i} is${isPrime(i) ? '' : ' not'} prime`);_x000D_
   }

This will cover all the possibility of a prime number . (order of the last 3 if statements is important)

   function isPrime(num){  
    if (num==0 || num==1) return false;
    if (num==2 || num==3 ) return true; 
    if (num % Math.sqrt(num)==0 ) return false;
    for (let i=2;i< Math.floor(Math.sqrt(num));i++) if ( num % i==0 ) return false;
    if ((num * num - 1) % 24 == 0) return true;        
   }

This calculates square differently and skips even numbers.

const isPrime = (n) => {
  if (n <= 1) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  //goto square root of number
  for (let i = 3, s = n ** 0.5; i < s; i += 2) {
    if (n % i == 0) return false;
  }
  return true;
};

This one is I think more efficient to check prime number :

function prime(num){
 if(num == 1) return true;
 var t = num / 2;
 var k = 2;
 while(k <= t) {
   if(num % k == 0) {
      return false
   } else {
   k++;  
  }
 }
  return true;
}
console.log(prime(37))

My Solution,

function isPrimeNumber(number){_x000D_
  if(number <= 1) return false;_x000D_
  if(number <= 3) return true;_x000D_
  for(let i = 2; i < 9; i++) {_x000D_
    if(number === i) continue;_x000D_
    if(number % i === 0 ) return false;_x000D_
  }  _x000D_
  return true;_x000D_
}_x000D_
_x000D_
for(let i = 0; i <= 100; i++){_x000D_
  if (isPrimeNumber(i)) console.log(i);_x000D_
}

function isPrimeNumber(n) {
  for (var i = 2; i < n; i++) { // i will always be less than the parameter so the condition below will never allow parameter to be divisible by itself ex. (7 % 7 = 0) which would return true
    if(n % i === 0) return false; // when parameter is divisible by i, it's not a prime number so return false
  }
  return n > 1; // otherwise it's a prime number so return true (it also must be greater than 1, reason for the n > 1 instead of true)
}

console.log(isPrimeNumber(1));  // returns false
console.log(isPrimeNumber(2));  // returns true
console.log(isPrimeNumber(9));  // returns false
console.log(isPrimeNumber(11)); // returns true

The only even prime number is 2, so we should exclude even numbers from the loop.

function isPrime(a) {
    if (a < 2) return false;
    if (a > 2) {
        if (a % 2 == 0) return false;
        for (let x = 3; x <= Math.sqrt(a); x += 2) {
            if (a % x == 0) return false;
        }
    }
    return true;
}

I think a better way to find a prime number is with this logic:

var p=prompt("input numeric value","10"); // input your number _x000D_
for(j=2;j<p;j++){ _x000D_
  if(isPrimes(j)){ _x000D_
    document.write(j+", "); // for output the value_x000D_
  } // end if_x000D_
}// end for loop_x000D_
function isPrimes(n) {_x000D_
  var primes = true;// let prime is true_x000D_
  for (i=2;i<n;i++) {_x000D_
    if(n%i==0) {_x000D_
      primes= false; // return prime is false_x000D_
      break; // break the loop_x000D_
    }// end if inner _x000D_
  }// end inner loop_x000D_
  return primes; // return the prime true or false_x000D_
}// end the function

I think this question is lacking a recursive solution:

// Preliminary screen to save our beloved CPUs from unneccessary labour_x000D_
_x000D_
const isPrime = n => {_x000D_
  if (n === 2 || n === 3) return true;_x000D_
  if (n < 2 || n % 2 === 0) return false;_x000D_
_x000D_
  return isPrimeRecursive(n);_x000D_
}_x000D_
_x000D_
// The recursive function itself, tail-call optimized._x000D_
// Iterate only over odd divisors (there's no point to iterate over even ones)._x000D_
 _x000D_
const isPrimeRecursive = (n, i = 3, limit = Math.floor(Math.sqrt(n))) => { _x000D_
  if (n % i === 0) return false;_x000D_
  if (i >= limit) return true; // Heureka, we have a prime here!_x000D_
  return isPrimeRecursive(n, i += 2, limit);_x000D_
}_x000D_
_x000D_
// Usage example_x000D_
_x000D_
for (i = 0; i <= 50; i++) {_x000D_
  console.log(`${i} is ${isPrime(i) ? `a` : `not a` } prime`);_x000D_
}

This approach have it's downside – since browser engines are (written 11/2018) still not TC optimized, you'd probably get a literal stack overflow error if testing primes in order of tens lower hundreds of millions or higher (may vary, depends on an actual browser and free memory).

Simple version:

function isPrime(num) {
    if (num <= 1) { 
        return false;
    } else {
        for (var i = 2; i < num; i++) {
            if (num % i === 0) {
                return false; 
            }
        }
        return true;
    }  
}

console.log(isPrime(9));

Using Ticked solution Ihor Sakaylyuk

const isPrime = num => {
        for(let i = 2, s = Math.sqrt(num); i <= s; i++)
            if(num % i === 0) return false; 
        return num !== 1 && num !== 0;
}

Gives in console

isPrime( -100 ) true

const isPrime = num => {
  // if not is_number num return false

  if (num < 2) return false

  for(let i = 2, s = Math.sqrt(num); i <= s; i++) {
        if(num % i === 0) return false
  }

  return true
}

Gives in console

isPrime( 1 ) false

isPrime( 100 ) false

isPrime( -100 ) false

First 6 primes ? 2 3 5 7 11 13 ?

isPrime( 1 ) false

isPrime( 2 ) true // Prime 1

isPrime( 3 ) true // Prime 2

isPrime( 4 ) false

isPrime( 5 ) true // Prime 3

isPrime( 6 ) false

isPrime( 7 ) true // Prime 4

isPrime( 8 ) false

isPrime( 9 ) false

isPrime( 10 ) false

isPrime( 11 ) true // Prime 5

isPrime( 12 ) false

isPrime( 13 ) true // Prime 6

You are trying to check too much conditions. just one loop is required to check for a prime no.

function isPrime(num){
if(num==2) 
return true;
for(i=2;i<Math.sqrt(num);i++) // mathematical property-no number has both of its factors greater than the square root 
{
if(num % i==0) 
return false; // otherwise it's a prime no.
}
return true;
}

You have to consider every no. a prime no. unless it is divisible by some no. less than or equal to the square root.

Your solution has got a return statement for every case,thus it stops execution before it should.It doesn't check any number more than once.It gives wrong answer for multiple cases-- 15,35.. in fact for every no. that is odd.

Prime numbers are of the form 6f ± 1, excluding 2 and 3 where f is any integer

 function isPrime(number)
 { 
   if (number <= 1)
   return false;

   // The check for the number 2 and 3
   if (number <= 3)
   return true;

   if (number%2 == 0 || number%3 == 0)
   return false;

   for (var i=5; i*i<=number; i=i+6)
   {
      if (number%i == 0 || number%(i+2) == 0)
      return false;
   }

   return true;
 }

Time Complexity of the solution: O(sqrt(n))

function isPrime(num) { // returns boolean
  if (num <= 1) return false; // negatives
  if (num % 2 == 0 && num > 2) return false; // even numbers
  const s = Math.sqrt(num); // store the square to loop faster
  for(let i = 3; i <= s; i += 2) { // start from 3, stop at the square, increment in twos
      if(num % i === 0) return false; // modulo shows a divisor was found
  }
  return true;
}
console.log(isPrime(121));

Thanks to Zeph for fixing my mistakes.

function isPrime(num) {
        if(num < 2) return false;
        for (var i = 2; i <= num/2; i++) {
            if(num%i==0)
                return false;
        }
        return true;
    }

If we want the prime number between two number we have to add this code only

for(var i = 0; i < 100; i++){
        if(isPrime(i))
            console.log(i);
    }

(function(value){
    var primeArray = [];
    for(var i = 2; i <= value; i++){ 
        if((i === 2) || (i === 3) || (i === 5) || (i === 7)){ 
            primeArray.push(i);
        }
          else if((i % 2 !== 0) && (i % 3 !== 0) && (i % 5 !== 0) && (i % 7 !== 0)){ 
              primeArray.push(i);
          }
        } 
       console.log(primeArray);
}(100));

Why are you trying to use loops!? Iterating is such a waste of computing power here...

This can be done using math:

function isPrime(num) {
    if ( num !=1 && num%3 != 0 && num%5 != 0 && num%7 != 0 && num%9 != 0 && num%11 != 0 && Math.sign(num) == 1 && Math.round(num) == num) {

        if ( (num-1)%6 == 0 || (num+1)%6 == 0 ) {
            return true;
        }

    } // no need for else statement since if true, then will do return
    return num==11||x==9||num==5||num==3||num==2; // will return T/F;
}

Steps:

1. Check if the number is divisible by 5 (evenly)
2. Check if the number is positive (negative numbers are not prime)
3. Check if the number is a whole number (5.236 by rule not prime)
4. Check if the number ± 1 is divisible by 6 (evenly)
   For more information check out 3Blue1Brown's Video
5. Check if the number is 2, 3, 9 or 11 (outliers with the rule)
6. Check if the number is 7 or 5 (due to attempt at false-positive reduction)

Always try to do the mathematical way, rather than iterating over loops. Math is almost always the most efficient way to do something. Yes, this equation might be confusing... However, we don't need much readability when it comes to checking if something is prime or not... It likely isn't going to need to be maintained by future code editors.

EDIT:
Optimized code version:

function isPrime(x=0) {
    const m = Math;
    return (x%3!=0&&x%5!=0&&x%7!=0&&x%9!=0&&x%11!=0&&x!=1&&m.sign(x)*m.round(x)==x&&(!!!((x-1)%6)||!!!((x+1)%6)))||x==11||x==9||x==7||x==5||x==3||x==2;
}

EDIT:
As it turns out... there's more to do with false-positive detection, because they're randomly distributed (at least seemingly) so the +-1 %6 stuff really isn't going to work for everything... But I'm definitely on to something here...

I would do it like this:

const isPrime = (num) => num < 10 ? [2, 3, 5, 7].includes(num) : ![2, 3, 5, 7].some(i => !(num % i));