How can the code be optimized to test for primeness?

Question

JavaScript

Here's what I got :

function isPrime(num) {
  for (var i = 2; i <= Math.sqrt(num);) {
    if (num % i == 0) return false;
    i == 2 ? i++ : i += 2;
  }
  return num > 1;
}

Is there any other way to optimize this code?

Answer 1

As I understand it, what is needed is not finding prime numbers, but an effective check of a number for simplicity. Your solution is a classic head-on solution, which, of course, works and gives a 100% accurate result. However, in addition to simply iterating over all numbers from 2 to sqrt(n), there are more efficient algorithms. Two optimization methods quickly come to mind:
1. If you do not need a direct guarantee of simplicity, then you can use the Rabin-Miller test . There are a number of numbers that are not prime but pass this test. You can read about them and add to the additional condition.
2. You can use the property of composite numbers that not only are they not divisible by numbers from the range 2 .. sqrt(n), but they are also not divisible by any of the prime numbers less than sqrt(n). If, after processing the isPrime function, the passed number is stored in an array, if it turned out to be prime, then it is possible to organize a loop not over the range 2 .. sqrt(n), but over an array of already known prime numbers.

Answer 2

function isPrime( num ) 
{
  if( num <= 1 )
    return false;

  for( i = 2; i * i <= num; i ++)
  { 
      if( num % i == 0 ) 
        return false;
  }
  return true;
}