isPrime in JavaScript

Harshit Jindal Oct 12, 2023
  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
isPrime 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).

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn