algorithm - 使用尾递归在 Scala 中实现 isPrime

Question

我正在做一个练习，它要求我使用尾递归在 scala 中实现 isPrime。我确实有一个实现，但是我在生成正确的基本案例时遇到了问题。

所以我的算法涉及检查从 2 到 N/2 的所有数字，因为 N/2 是 N 的最大因数。

def isPrime(n: Int): Boolean = {
    def isPrimeUntil(t: Int): Boolean = {
        if(t == 2) true
        else n % t != 0 && isPrimeUntil(t - 1)
    }

    isPrimeUntil(n/2)
}

所以基本上如果我想检查 15 是否是质数，我会检查从 7 到 2 的所有数字。

这是我的踪迹:

isPrimeUntil(7) -> true && isPrimeUntil(6)-> true && isPrimeUntil(5)-> false && isPrimeUntil(4)

由于短路评估，函数此时返回 false。

但是，对于检查 3 是否为质数的基本情况，我的实现失败了。

Answer 1

3 不是您唯一的问题。它还为 4 返回 true ...您的基本情况应该是 1，而不是 2:

   def isPrimeUntil(t: Int): Boolean = t == 1 || t > 1 && n%t != 0 && isPrimeUntil(t-1)