Enhancements and tail recursion for pure functional Primality Test in Scala

[greg-a-atkinson]

Hi Alessio, thanks for the article A pure functional Primality Test in Scala

I propose for consideration, with regards to:

    def isPrime(n: Int)(implicit i: Int = 5): Boolean =
    {
        if (n <= 3)
            return n > 1
        if (n % 2 == 0 || n % 3 == 0)
            return false
        while (i * i <= n)
        {
            if (n % i == 0 || n % (i + 2) == 0)
                return false
            return isPrime(n)(i + 6)
        }
        true
    }

That:

1. The condition (n <= 3):
   1.1. Needs to be evaluated at most once.
2. The condition (n % 2 == 0 || n % 3 == 0):
   2.1. Needs to be evaluated at most once.
   2.2. The is-even test (n % 2 == 0) is likely more efficient as ((n & 1) == 0), but a JMH micro-benchmark would be required to confirm this.
3. The statement while (i * i <= n):
   3.1. The while-statement executes at most once, so can be replaced by an if-statement.
   3.2. Int.MaxValue is prime, but i*i will eventually overflow Int, become negative, incorrectly satisfy i * i <= n and declare Int.MaxValue not prime. (That's when tail-recursive, the current implementation throws a StackOverflowError for isPrime(Int.MaxValue) before getting that far.)
   3.3. i * i <= n can be replaced by i <= sqrt(n), where sqrt(n) is evaluated once and Int overflow is avoided.
4. The repetitive component of the primality test can be marked tail-recursive for further compiler optimisation.
   4.1. There are differing styles for defining the recursive function, as already mentioned in the comments so far. But avoiding default parameters, implicits and nested functions with simple private scope is probably sufficient.

  def isPrime(n: Int): Boolean =
    if (n <= 3) n > 1
    else if ((n & 1) == 0 || n % 3 == 0) false
    else isPrime(n, 5, Math.sqrt(n).floor.toInt)

  @scala.annotation.tailrec
  private def isPrime(n: Int, i: Int, maxI: Int): Boolean =
    if (i <= maxI) {
      if (n % i == 0 || n % (i + 2) == 0) false
      else isPrime(n, i + 6, maxI)
    } else true

Corrections and further optimisations welcome.

Thanks

Kind regards,
Greg