isPrime in JavaScript

1. Naïve Solution to Check if a Number Is Prime in JavaScript
2. Square Root Solution to Check if a Number Is Prime in JavaScript

A prime number is higher than one with two factors - one and itself. It means that prime numbers always leave a remainder whenever divided by other numbers. The other numbers greater than one with more than two factors are called composite numbers.

This article will discuss different methods to check if a number is prime in JavaScript.

Naïve Solution to Check if a Number Is Prime in JavaScript

The easiest way to check if a number n is prime is to iterate from 2 to n-1 then check if n is divisible by each of them.

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

console.log(isPrime(70));
console.log(isPrime(23));

Time Complexity

We iterate n-2 times from 2 to n-1. This solution’s time complexity is O(n).

Space Complexity

This solution’s space complexity is O(1).

Square Root Solution to Check if a Number Is Prime in JavaScript

The solution above can improve by iterating only until sqrt(n). It’s based on the fact that sqrt(n) * sqrt(n) = n, and there has to be at least one factor less than equal to sqrt(n). If we can’t find any factor in the range of [2, sqrt(n)], it means the number n is a prime number.

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

console.log(isPrime(70));
console.log(isPrime(23));

Time Complexity

Since we iterate the first sqrt(n) potential factors, the time complexity of the above solution is sqrt(n).

Space Complexity

This solution’s space complexity is O(1).