在 Scala 中检查一个数是否为素数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/36882103/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Checking whether a number is prime in Scala
提问by Arnab
I wanted to check if a number is prime or not. I wrote the following code, but it does not return any value:
我想检查一个数字是否为质数。我写了以下代码，但它不返回任何值：
def isprime(x:Int) = {
| if (x==1) false
| else {
| for (i <- 2 to x-1) {
| if (x % i == 0) false
| else true
| }
| }
| }
回答by eliasah
What you did is a called defining a function so obviously it won't return anything and as a matter of fact, this function returns AnyVal which obviously won't help you much. I suspect that you actually need a Boolean type returned.
你所做的是定义一个函数的调用，所以显然它不会返回任何东西，事实上，这个函数返回 AnyVal ，这显然对你没有多大帮助。我怀疑您实际上需要返回一个布尔类型。
Since you are working with the REPL, you would want to define your function to check if a number is prime. I called it isPrime2and then test it.
由于您正在使用 REPL，因此您需要定义函数来检查数字是否为质数。我调用它isPrime2然后测试它。
def isPrime2(i :Int) : Boolean = {
| if (i <= 1)
| false
| else if (i == 2)
| true
| else
| !(2 to (i-1)).exists(x => i % x == 0)
| }
// isPrime2: (i: Int)Boolean
(1 to 10).foreach(i => if (isPrime2(i)) println("%d is prime.".format(i)))
// 2 is prime.
// 3 is prime.
// 5 is prime.
// 7 is prime.
I would even suggest a simpler version if you care not using if else conditions :
如果您不在乎使用 if else 条件，我什至会建议一个更简单的版本：
def isPrime1(n: Int): Boolean = ! ((2 until n-1) exists (n % _ == 0))
Which also returns a Boolean.
这也返回一个布尔值。
EDIT:
编辑：
As @TheArchetypalPaul stated, which was also implied, the problem is that your for loop isn't resulting in any value - you calculate a true/false value, but then don't do anything with it. So your else clause doesn't result in any value (in fact, it produces Unit). You need to return false as soon as you find a divisor - and the way to do that is probably exists as in isPrime1.
正如@TheArchetypalPaul 所说，这也暗示了，问题是你的 for 循环没有产生任何值 - 你计算一个真/假值，但不要对它做任何事情。因此，您的 else 子句不会产生任何值（实际上，它会产生Unit）。您需要在找到除数后立即返回 false - 这样做的方法可能存在于isPrime1.
回答by Mahesh Chand
One liner Solution
一个班轮解决方案
def isPrime(num:Int):Boolean =
(num > 1) && !(2 to scala.math.sqrt(num).toInt).exists(x =>num % x == 0)
回答by kanbagoly
This one is less elegant than the one liners, but a bit faster. It uses the fact that all primes (except 2 and 3) have to be at 6k±1. So it skips testing numbers which are dividable by 2 or 3. It will only test for the groups of (5, 7), (11, 13), (17, 19) and so on.
这个不如 one liner 优雅，但快一点。它利用了所有质数（2 和 3 除外）都必须在 的事实6k±1。因此它会跳过可被 2 或 3 整除的测试数字。它只会测试 (5, 7)、(11, 13)、(17, 19) 等组。
def isPrime(number: Int): Boolean =
if (number < 4) number > 1
else if (number % 2 == 0 || number % 3 == 0) false
else (5 to math.sqrt(number).toInt by 6).forall(i => number % i != 0 && number % (i + 2) != 0)
回答by TheQuestioner
Here is another one liner:
这是另一个班轮：
def isPrime(num: Int): Boolean = (2 to num) forall (x => num % x != 0)
forallwill check if the predicate holds for all elements of this range
forall将检查谓词是否适用于此范围的所有元素
I just realised that the code above is a bit slow for bigger numbers, so here an improved version:
我刚刚意识到上面的代码对于更大的数字有点慢，所以这里有一个改进的版本：
def isPrime(n: Int): Boolean = (2 to math.sqrt(n).toInt) forall (x => n % x != 0)
回答by Teimuraz
Here is one more 1 line solution:
这是另一种 1 行解决方案：
def isPrime(n: Int) = Range(2, n-1).filter(i => n % i == 0).length == 0
Or even shorter:
或者更短：
def isPrime(n: Int) = Range(2, n-1).filter(n % _ == 0).length == 0
回答by arpanchaudhury
This can be a solutions.
这可以是一个解决方案。
def isPrime(integer: Int): Boolean = {
if (integer == 1) false
else {
val domain = (2 to math.sqrt(integer).toInt).view
val range = domain filter (isDivisibleBy(integer, _))
range.isEmpty
}
}
def isDivisibleBy(integer: Int, divisor: Int): Boolean = integer % divisor == 0
Now coming back to the code that you have written, your code returns AnyValand desired return type should be Boolean. And the reason behind that is in Scala (or any functional language) for loop is an expressionnot a control structure.
现在回到您编写的代码，您的代码返回AnyVal并且所需的返回类型应该是Boolean。这背后的原因是在 Scala（或任何函数式语言）中 for 循环是一个表达式而不是一个控制结构。
回答by Epicurist
Comment on the former answers (except @jwvh): there is no need to use even numbers more than once. After a test by 2, the domain 3 to math.sqrt(integer).toInt by 2must be used.
评论以前的答案（@jwvh 除外）：没有必要多次使用偶数。经过2次测试后，3 to math.sqrt(integer).toInt by 2必须使用该域。
I have developed an accelerated tail-recursive version. It skips even values, and test two values in one go.
我开发了一个加速尾递归版本。它跳过偶数值，并一次性测试两个值。
See it for yourself, running in your browser Scastie (remote JVM).
亲自查看，在浏览器中运行Scastie (remote JVM)。
import java.lang.System.currentTimeMillis
import scala.annotation.tailrec
import scala.collection.immutable.TreeSet
import scala.io.Source
// Primality by trial division
object PrimesTestery extends App {
val oeisPrimes = TreeSet(oeisPrimesText.map(_.toInt): _*)
def oeisPrimesText = rawText.getLines.takeWhile(_.nonEmpty).map(_.split(" ")(1)).toList
def rawText = Source.fromURL("https://oeis.org/A000040/a000040.txt")
def isPrime(n: Long) = {
val end = math.sqrt(n.toDouble).toInt
@tailrec
def inner(d: Int): Boolean = {
(d > end) || (n % d != 0 && n % (d + 2) != 0) && inner(d + 6)
}
n > 1 && ((n & 1) != 0 || n == 2) && (n % 3 != 0 || n == 3) && inner(5)
}
println(s"Found ${oeisPrimes.size} primes on OEIS , last is ${oeisPrimes.last}.")
for (i <- (0 to oeisPrimes.last))
assert(isPrime(i.toLong) == oeisPrimes.contains(i), s"Wrong $i")
println(s"? Successfully completed without errors. [total ${currentTimeMillis - executionStart} ms]")
}
To be sure, this code test against the known list of primes for primes ánd composite numbers.
可以肯定的是，此代码针对素数和合数的已知素数列表进行测试。
回答by chaotic3quilibrium
Many of the solutions in the answers to this question appear to either not work, haven't covered obvious edge cases, and/or are blatantly inefficient.
这个问题的答案中的许多解决方案似乎要么不起作用，要么没有涵盖明显的边缘情况，和/或效率低下。
Below is my answer which works, covers all edge cases, and is as efficient as it is possible to be in this particular domain; i.e. it checks as few values as possible and it fails early as possible if the number isn't a prime.
下面是我的答案，它有效，涵盖了所有边缘情况，并且在这个特定领域中尽可能高效；即它检查尽可能少的值，如果数字不是质数，它会尽早失败。
def isPrime(long: Long): Boolean =
if (long > 8L) {
!(((long % 2L) == 0L)
|| (3L to math.sqrt(long).toLong by 2L).exists(n => (long % n) == 0L))
} else
(long > 1L) && ((long == 2L) || ((long % 2L) != 0L))
UPDATE (2019/09/18):I stand corrected about my solution being "is as efficient as it is possible to be in this particular domain". The solution provided by @kanbagolyis actually more efficient in that it has fewer checks. His is implemented using Int. Here's his solution reimplemented using Longjust in case you want to only do a copy/paste and not run into stupid Intversus Longissues:
更新（2019 年 9 月 18 日）：我纠正了我的解决方案“在这个特定领域尽可能高效”。@kanbagoly 提供的解决方案实际上更有效，因为它的检查更少。他是使用Int. 下面是使用他的解决方案重新实现Long，以防万一你只想做一个复制/粘贴，并没有碰到傻Int与Long问题：
def isPrime(long: Long): Boolean =
if (long < 4L)
long > 1L
else if (((long % 2L) == 0L) || ((long % 3L) == 0L))
false
else
(5L to math.sqrt(long).toLong by 6L).forall(n => ((long % n) != 0L) && ((long % (n + 2L)) != 0L))
回答by Igor Dorokhov
def isPrime(n: Int) = (2 until n) forall(x => n % x !=0)
回答by Arash Ahmadi
also you can use this recursive function:
你也可以使用这个递归函数：
def isPrime(n: Int):Boolean = {
def isPrimeUntil(t: Int): Boolean =
if (t<=1) true
else n%t != 0 && isPrimeUntil(t-1)
isPrimeUntil(n/2)
}
