How to Efficiently Determine if a Number is Prime in JavaScript?

Prime Number Checking in JavaScript

This article addresses the problem of determining if a given number is prime or not using JavaScript. A prime number is an integer greater than 1 that is not divisible by any other natural number except 1 and itself.

Solution 1

The traditional method involves iterating from 2 to the square root of the input number and checking if the number is divisible by any of these. If it is, it's not prime; otherwise, it is.

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

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

An alternative approach utilizes the fact that a prime number greater than 2 cannot be odd. Thus, it suffices to check divisibility by 2 and then by odd numbers up to the square root of the input number. This optimization reduces the execution time significantly.

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

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