检查是否 n
时在Scala中是质数,最常见的解决方案是简洁的一行,几乎在SO上所有类似的问题中都可以看到
def isPrime1(n: Int) = (n > 1) && ((2 until n) forall (n % _ != 0))
继续,重写它以仅检查奇数很简单
def isPrime2(n: Int): Boolean = {
if (n < 2) return false
if (n == 2) return true
if (n % 2 == 0) false
else (3 until n by 2) forall (n % _ != 0)
}
但是,为了提高效率,我想将仅检查赔率与计数相结合 sqrt(n)
, 但不使用 Math.sqrt
.所以,作为 i < sqrt(n) <==> i * i < n
,我会写类似 C 的循环:
def isPrime3(n: Int): Boolean = {
if (n < 2) return false
if (n == 2) return true
if (n % 2 == 0) return false
var i = 3
while (i * i <= n) {
if (n % i == 0) return false
i += 2
}
true
}
问题是:
1) 如何在第一个版本中实现最后一个版本漂亮的Scala 功能风格?
2) 如何使用 Scala for
对此?我想到了类似于下面的东西,但不知道怎么做。
for {
i <- 3 until n by 2
if i * i <= n
} { ??? }
最佳答案
这是一种在 sqrt(n)
之前验证 n 是否为素数而不使用 sqrt
的方法:
def isPrime3(n: Int): Boolean = {
if (n == 2) {
true
} else if (n < 2 || n % 2 == 0) {
false
} else {
Stream.from(3, 2).takeWhile(i => i * i < n + 1).forall(i => n % i != 0)
}
}
如果你想一直执行到n/2,这也是一个可能的优化(比sqrt(n)
),你可以将最后一行替换为:
(3 to n/2 + 1 by 2).forall(i => n % i != 0)
如果您愿意,您还可以制作尾递归版本,大致如下:
import scala.annotation.tailrec
def isPrime3(n: Int): Boolean = {
if (n == 2 || n == 3) {
true
} else if (n < 2 || n % 2 == 0) {
false
} else {
isPrime3Rec(n, 3)
}
}
@tailrec
def isPrime3Rec(n:Int, i: Int): Boolean = {
(n % i != 0) && ((i * i > n) || isPrime3Rec(n, i + 2))
}
关于scala - 在 Scala 的 O(sqrt(n)) 中检查数字是否为质数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43293233/