How to Efficiently Check for Prime Numbers in JavaScript?

How to Determine Prime Numbers in JavaScript

In JavaScript, identifying prime numbers is a common programming task. A prime number is a positive integer greater than 1 that is not divisible by any other positive integer except 1 and itself.

Solution 1: Naive Approach

The provided code snippet offers a simple way to check if a number is prime:

<code class="js">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true;

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? isPrime *= false : isPrime *= true;
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

Time Complexity: O(sqrt(n))

Space Complexity: O(1)

Solution 2: Efficient Approach

An improved approach for checking prime numbers is:

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

This code takes advantage of the fact that if a number is not prime, it has a factor that is less than or equal to its square root. By checking for factors up to the square root, we can efficiently eliminate potential factors.

Time Complexity: O(sqrt(n))

Space Complexity: O(1)

The above is the detailed content of How to Efficiently Check for Prime Numbers in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!