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

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

primes scala algorithm

Mutating Algorithm · 技术社区 · 6 年前

我正在做一个练习,它要求我使用尾部递归在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 回复 | 直到 6 年前

Dima 6 年前

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

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

SergGr 6 年前

虽然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) )

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前