代码之家 › 专栏 › 技术社区 › Mutating Algorithm

使用尾部递归在scala中实现isprime

primes scala algorithm

2

Mutating Algorithm · 技术社区 · 7 年前

我正在做一个练习,它要求我使用尾部递归在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是否为prime的基本情况,我的实现失败。

2 回复 | 直到 7 年前

1

2

Dima 7 年前

3不是你唯一的问题。它还会回来 true 对于 4 … 你的基本情况应该是 1 不是 2 :

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

2

1

SergGr 7 年前

虽然Krzystof正确地指出了问题的根源是整数除法,但我不喜欢他的解决方案。我相信正确的方法是把测试改为

 if(t <= 2) true

在这种情况下 n = 3 如此 n/2 = 1 它不会停下来 t = 0 .

一些好处:

修改后的支票 (t <= 2) 在几乎所有的现代硬件上都像 (t == 2)
我觉得它能更好地传达逻辑
写东西效率很低 (n.toDouble/2).ceil.toInt 那样。写起来越来越容易 (n+1)/2 而不是进行2次转换(到double并返回int)
它不需要对所有奇数进行过多的检查 n ( (n+1)/ 2 不是奇数的最小除数 n 两者之间有区别的地方 n/2 和 ceil(n/2) )