How can you efficiently determine if a number is prime in JavaScript?

Efficiently Verifying Prime Numbers in JavaScript

In computer programming, determining if a given number is prime is a fundamental task. A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself.

A popular approach to checking for primality involves the Sieve of Eratosthenes. However, for performance considerations, a more efficient method can be employed, as demonstrated in the following JavaScript implementation:

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 and Space Complexity Analysis

The time complexity of the above algorithm is O(sqrt(n)), where n represents the input value. This is because the loop iterates through all integers up to the square root of the input number, which is a significant optimization over checking all integers up to n.

The space complexity is O(1), as it does not require any additional data structures beyond primitive variables.

Alternative Approach

An alternative syntax for checking primality in JavaScript is:

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

This approach achieves the same time and space complexity as the previous one while utilizing a more concise arrow function syntax.

The above is the detailed content of How can you efficiently determine if a number is prime in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!