Scalaで素数判定 試し割り法

試し割り法

自然数nが$2 \leq k \leq \sqrt n$となる全ての自然数kで割り切れない場合は素数、一つでも割り切れるkが存在する場合素数でないとする判定方法です。

Scalaのコード

for式使用版

ループにより実装したコードです。

  def isPrime(n: Int): Boolean = {

    if (n < 2 || (n > 2 && n % 2 == 0)) {
      return false
    } else if (n == 2) {
      return true
    }

    for (i <- 3 to Math.sqrt(n).toInt by 2 ) {

      if (n % 3 == 0) {
        return false
      }
    }

    return true
  }

再帰呼び出し版

再帰呼び出しを使ってfor式を無くしたコードです。
scala.annotation.tailrecアノテーションを使って末尾再帰になっているかチェックしています。

  def isPrime(n: Int): Boolean = {

    if (n < 2 || (n > 2 && n % 2 == 0)){
      return false
    } else if (n == 2) {
      return true
    }


    @annotation.tailrec
    def loop(n: Int, m: Int): Boolean = {

      if (m * m > n) {
        return true
      } else if (n % m == 0) {
        return false
      } else {
        loop(n, m + 2)
      }
    }

    loop(n, 3)
  }