Today’s Codewars kata was Is a Number Prime?, which was a basic test to determine if a given int was a prime number.

// ignoring 0, 1, and 2
for (int i = 5; i <= num/2; i++)
  if (num % i == 0) return false;
return true;

But it cautioned against brute forcing the answer by building a loop that tests every int up to n/2. So I had to go looking for a more efficient test.

Wikipedia’s Primalty Test page provides some basic code for doing this test, plus explanation for how it works. Because all divsor pairs of an integer n include a divisor less than or equal to the square root of n, we can limit our loop to Math.sqrt(num).

for (int i = 5; i <= Math.sqrt(num); i++)
  if (num % i == 0) return false;
return true;

Additionally, we only need to look for prime divisors of num, because non-prime divisors are, naturally, also divisible by a smaller number. 2 and 3 should be tested, and primes >= 5 have the form 6n +-1.

for (int i = 5; i <= Math.sqrt(num); i = i+6)
  if (num % i == 0 || num % (i+2) == 0) return false;
return true;

Then we just need to acknowledge 0, 1, 2, and the negative numbers.

public static boolean isPrime(int num) {
    if (num <= 1)
      return false;
    if (num == 2 || num == 3) // test these before testing mod
      return true;
    if (num % 2 == 0 || num % 3 == 0)
      return false;
    for (int i = 5; i <= Math.sqrt(num); i = i + 6)
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    return true;
  }

Then we look at the solutions and see that everyone ignored the caution about brute forcing every single int, and we also see that Java’s BigInteger class has a method called isProbablePrime that just does the work for you with whatever certainty you want it to have.