-1

I wrote this function to check if a number 'n' is a prime:

int isPrime(const long long int n) {
  long long int d = 3; /* Division by 0 has no meaning.
                          Any number is perfectly divisible by 1.
                          And any even number greather then 2 is not a prime
                          number (we'll perform a separate check for 2).
                          So we shall start the division at 3. */

  if (n <= 1)
    return 0; // 0 and 1 are not prime numbers.

  if (n == 2)
    return 1; // 2 is the only even prime number.

  if (n % 2 == 0)
    return 0; /*  If 'n' is an even number other than 2 (see above), by
                  definition it can not be a prime number. */

  while ((d * d) < (n / 2)) /*  Looking for an integer proper divisor of 'n' (with 'n' is an
                                odd number) smaller than sqrt(a/2). */
  {
    if (n % d == 0)
      return 0; // Looking for a proper divisor other then 1.

    d += 2; // We skeep even numbers.
  }
  return 1; /* If there does not exist a proper divisor other then 1, by
               definition 'n' is prime number. */
}

I wonder if anyone knows a more efficient way to accomplish this task.

Bey Réda
  • 21
  • 4
  • 3
    Miller-Rabin test is the industry standard. – Eugene Sh. May 31 '22 at 16:39
  • If you aren't going far into the primes, like up to a hundred or so, you can always use a lookup table – yosmo78 May 31 '22 at 16:40
  • `while ((d * d) < (n / 2))` can be changed to `while (d <= n / d)`. – Ian Abbott May 31 '22 at 16:41
  • It would be more efficient if you only use primes previously found as potential divisors (if you are making a list). – Weather Vane May 31 '22 at 16:42
  • 1
    For making a list there is the ancient Eratosthenes algorithm. – Eugene Sh. May 31 '22 at 16:43
  • 4
    Shouldn't the loop be `while (d * d <= n)` ? (Or work with a precalculated square root). – Weather Vane May 31 '22 at 16:45
  • Are you sure it has to be (d <= n / d) ? (d < n / d) isn't sufficient since I'm filtering even numbers? – Bey Réda May 31 '22 at 16:47
  • 3
    You won't find say 7 * 7 = 49 without the <= to include equality. Also note that multiplication is usually more efficient than division. – Weather Vane May 31 '22 at 16:48
  • As you are aware, you don't need to search up to N-1; up to and including `ceil(sqrt(N))` is sufficient. If N is composite, then one factor is not larger than √N and the other is not smaller than √N). After you've checked for 'divisible by 2', you could check only the odd numbers. If you check for 'divisible by 3' outside the loop, then all bigger primes have the form 6K±1 for an integer K starting at K equal to 1. Limiting the search range gives a radical speedup even when N is just in the thousands, let alone much bigger. Using 'odds only' does 1/2 the work; using 6K±1 does 1/3. – Jonathan Leffler May 31 '22 at 16:48
  • If the range to be searched is big enough (the maximum value is large enough), building a Sieve of Eratosthenes (or even more advanced techniques — such as Sieve of Atkin) for the primes up to the square root of the maximum and then testing only the 'known to be prime' possible factors can be beneficial. Eventually, deterministic evaluation of 'is it a prime' becomes too slow and you resort to probabilistic prime detection such as the Miller-Rabin test. See Wikipedia on [Primality test](https://en.wikipedia.org/wiki/Primality_test). – Jonathan Leffler May 31 '22 at 16:48
  • 1
    If not storing a list, you can also do `skip = 2;` `while (...) {` `if (n % d == 0) return 0;` `d += skip;` `skip = 6 - skip;` `}` `return 1;` to reduce the number of candidates by 50%. This can be extended to check for candidates modulo 30 instead of modulo 6. – Ian Abbott May 31 '22 at 16:57
  • @WeatherVane Yes, `d * d <= n` is more efficient but also more prone to overflow. – Ian Abbott May 31 '22 at 16:58
  • 1
    The condition in the `while` loop is definitely wrong. Consider `n = 143`. The loop becomes `while (d*d < 71)` which allows a maximum of 8 for `d`. But `143 = 11 * 13` – user3386109 May 31 '22 at 17:00
  • 1
    @IanAbbott true, and the precalculated square root is better. – Weather Vane May 31 '22 at 17:00
  • @WeatherVane True unless looking for a list of prime factors when `n` can be divided by each factor as it is found. There is probably a way to combine the `%` and `/` operations into a single `div()`. – Ian Abbott May 31 '22 at 17:05
  • @WeatherVane The compiler might optimize the `n / d` followed by a `n % d` using a single `idiv`. See e.g. https://godbolt.org/z/z6vs1WaPb – Bob__ May 31 '22 at 17:08
  • answer depends on the number magnitude and even usage of the test ... the fastest is usually SoE (but requires memory so there is a limit for magnitude) then there are hybrid methods like [LUT + SoE + division test](https://stackoverflow.com/a/22477240/2521214) however for really big numbers you need probability based approaches like [Miller–Rabin primality test](https://en.wikipedia.org/wiki/Miller–Rabin_primality_test) ... on top of this you add otimization of code just compare mine first link with your routine and see the differences – Spektre Jun 01 '22 at 08:10
  • Correction: the alternating 2, 4 skip mentioned in my previous comment reduces the number of candidates by 1/3rd (33%) not 50%. – Ian Abbott Jun 01 '22 at 08:51

0 Answers0