Number prime test in JavaScript

Time complexity: O(sqrt(n))

Space complexity: O(1)

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

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


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.

Tags:

Javascript