使用 Scala 查找素数。帮助我改进
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9711785/
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
Find prime numbers using Scala. Help me to improve
提问by Kevin
I wrote this code to find the prime numbers less than the given number i in scala.
我编写这段代码是为了在 Scala 中找到小于给定数 i 的素数。
def findPrime(i : Int) : List[Int] = i match {
case 2 => List(2)
case _ => {
val primeList = findPrime(i-1)
if(isPrime(i, primeList)) i :: primeList else primeList
}
}
def isPrime(num : Int, prePrimes : List[Int]) : Boolean = prePrimes.forall(num % _ != 0)
But, I got a feeling the findPrime function, especially this part:
但是，我对 findPrime 函数有一种感觉，尤其是这部分：
case _ => {
val primeList = findPrime(i-1)
if(isPrime(i, primeList)) i :: primeList else primeList
}
is not quite in the functional style.
不太符合功能风格。
I am still learning functional programming. Can anyone please help me improve this code to make it more functional.
我还在学习函数式编程。任何人都可以帮助我改进此代码以使其更实用。
Many thanks.
非常感谢。
回答by Rahel Lüthy
Here's a functional implementation of the Sieve of Eratosthenes, as presented in Odersky's "Functional Programming Principles in Scala" Courseracourse :
这是 Eratosthenes 筛子的函数式实现，如Odersky 的“Scala 中的函数式编程原则”Coursera课程中所述：
// Sieving integral numbers
def sieve(s: Stream[Int]): Stream[Int] = {
s.head #:: sieve(s.tail.filter(_ % s.head != 0))
}
// All primes as a lazy sequence
val primes = sieve(Stream.from(2))
// Dumping the first five primes
print(primes.take(5).toList) // List(2, 3, 5, 7, 11)
回答by schmmd
The style looks fine to me. Although the Sieve of Eratosthenes is a very efficient way to find prime numbers, your approach works well too, since you are only testing for division against known primes. You need to watch out however--your recursive function is not tail recursive. A tail recursive function does not modify the result of the recursive call--in your example you prepend to the result of the recursive call. This means that you will have a long call stack and so findPrime will not work for large i. Here is a tail-recursive solution.
这种风格对我来说很好。尽管 Eratosthenes 筛法是一种非常有效的查找素数的方法，但您的方法也很有效，因为您只是在测试与已知素数的除法。但是，您需要注意——您的递归函数不是尾递归的。尾递归函数不会修改递归调用的结果——在您的示例中，您将递归调用的结果放在前面。这意味着您将有一个很长的调用堆栈，因此 findPrime 不适用于大 i。这是一个尾递归解决方案。
def primesUnder(n: Int): List[Int] = {
require(n >= 2)
def rec(i: Int, primes: List[Int]): List[Int] = {
if (i >= n) primes
else if (prime(i, primes)) rec(i + 1, i :: primes)
else rec(i + 1, primes)
}
rec(2, List()).reverse
}
def prime(num: Int, factors: List[Int]): Boolean = factors.forall(num % _ != 0)
This solution isn't prettier--it's more of a detail to get your solution to work for large arguments. Since the list is built up backwards to take advantage of fast prepends, the list needs to be reversed. As an alternative, you could use an Array, Vectoror a ListBufferto append the results. With the Array, however, you would need to estimate how much memory to allocate for it. Fortunately we know that pi(n)is about equal to n / ln(n)so you can choose a reasonable size. Arrayand ListBufferare also a mutable data types, which goes again your desire for functional style.
这个解决方案并不漂亮——它更多的是让您的解决方案适用于大型参数的细节。由于列表是反向构建以利用快速前置，因此需要反转列表。作为替代方案，您可以使用Array,Vector或 aListBuffer来附加结果。Array但是，对于，您需要估计要为其分配多少内存。幸运的是，我们知道这pi(n)大约等于，n / ln(n)因此您可以选择合理的尺寸。 Array并且ListBuffer也是可变数据类型，这再次满足了您对函数式风格的渴望。
Update: to get good performance out of the Sieve of Eratosthenes I think you'll need to store data in a native array, which also goes against your desire for style in functional programming. There might be a creative functional implementation though!
更新：为了从 Eratosthenes Sieve 中获得良好的性能，我认为您需要将数据存储在本机数组中，这也违背了您对函数式编程风格的渴望。不过可能有一个创造性的功能实现！
Update: oops! Missed it! This approach works well too if you only divide by primes less than the square root of the number you are testing! I missed this, and unfortunately it's not easy to adjust my solution to do this because I'm storing the primes backwards.
更新：哎呀！错过了！如果您只除以小于您正在测试的数字的平方根的素数，这种方法也很有效！我错过了这一点，不幸的是，调整我的解决方案来做到这一点并不容易，因为我正在向后存储质数。
Update: here's a very non-functional solution that at least only checks up to the square root.
更新：这是一个非常非功能性的解决方案，至少只检查平方根。
rnative, you could use an Array, Vectoror a ListBufferto append the results. With the Array, however, you would need to estimate how much memory to allocate for it. Fortunately we know that pi(n)is about equal to n / ln(n)so you can choose a reasonable size. Arrayand ListBufferare also a mutable data types, which goes again your desire for functional style.
rnative，你可以使用一个Array，Vector或ListBuffer对结果追加。Array但是，对于，您需要估计要为其分配多少内存。幸运的是，我们知道这pi(n)大约等于，n / ln(n)因此您可以选择合理的尺寸。 Array并且ListBuffer也是可变数据类型，这再次满足了您对函数式风格的渴望。
Update: to get good performance out of the Sieve of Eratosthenes I think you'll need to store data in a native array, which also goes against your desire for style in functional programming. There might be a creative functional implementation though!
更新：为了从 Eratosthenes Sieve 中获得良好的性能，我认为您需要将数据存储在本机数组中，这也违背了您对函数式编程风格的渴望。不过可能有一个创造性的功能实现！
Update: oops! Missed it! This approach works well too if you only divide by primes less than the square root of the number you are testing! I missed this, and unfortunately it's not easy to adjust my solution to do this because I'm storing the primes backwards.
更新：哎呀！错过了！如果您只除以小于您正在测试的数字的平方根的素数，这种方法也很有效！我错过了这一点，不幸的是，调整我的解决方案来做到这一点并不容易，因为我正在向后存储质数。
Update: here's a very non-functional solution that at least only checks up to the square root.
更新：这是一个非常非功能性的解决方案，至少只检查平方根。
import scala.collection.mutable.ListBuffer
def primesUnder(n: Int): List[Int] = {
require(n >= 2)
val primes = ListBuffer(2)
for (i <- 3 to n) {
if (prime(i, primes.iterator)) {
primes += i
}
}
primes.toList
}
// factors must be in sorted order
def prime(num: Int, factors: Iterator[Int]): Boolean =
factors.takeWhile(_ <= math.sqrt(num).toInt) forall(num % _ != 0)
Or I could use Vectors with my original approach. Vectors are probably not the best solution because they don't have the fasted O(1) even though it's amortized O(1).
或者我可以将Vectors 与我原来的方法一起使用。 Vectors 可能不是最好的解决方案，因为它们没有禁食 O(1)，即使它摊销了 O(1)。
回答by Jed Wesley-Smith
As schmmd mentions, you want it to be tail recursive, and you also want it to be lazy. Fortunately there is a perfect data-structure for this: Stream.
正如 schmmd 提到的，您希望它是尾递归的，并且您还希望它是惰性的。幸运的是，有一个完美的数据结构：Stream.
This is a very efficient prime calculator implemented as a Stream, with a few optimisations:
这是一个非常高效的素数计算器，实现为Stream，并进行了一些优化：
object Prime {
def is(i: Long): Boolean =
if (i == 2) true
else if ((i & 1) == 0) false // efficient div by 2
else prime(i)
def primes: Stream[Long] = 2 #:: prime3
private val prime3: Stream[Long] = {
@annotation.tailrec
def nextPrime(i: Long): Long =
if (prime(i)) i else nextPrime(i + 2) // tail
def next(i: Long): Stream[Long] =
i #:: next(nextPrime(i + 2))
3 #:: next(5)
}
// assumes not even, check evenness before calling - perf note: must pass partially applied >= method
def prime(i: Long): Boolean =
prime3 takeWhile (math.sqrt(i).>= _) forall { i % _ != 0 }
}
Prime.isis the prime check predicate, and Prime.primesreturns a Streamof all prime numbers. prime3is where the Stream is computed, using the prime predicate to check for all prime divisors less than the square root of i.
Prime.is是质数检查谓词，并Prime.primes返回Stream所有质数的 a。prime3是计算 Stream 的地方，使用素数谓词检查所有小于 的平方根的素数除数i。
回答by pathikrit
/**
* @return Bitset p such that p(x) is true iff x is prime
*/
def sieveOfEratosthenes(n: Int) = {
val isPrime = mutable.BitSet(2 to n: _*)
for (p <- 2 to Math.sqrt(n) if isPrime(p)) {
isPrime --= p*p to n by p
}
isPrime.toImmutable
}
回答by GordonBGood
@mfa has mentioned using a Sieve of Eratosthenes - SoEand @Luigi Plinge has mentioned that this should be done using functional code, so @netzwerg has posted a non-SoE version; here, I post a "almost" functional version of the SoE using completely immutable state except for the contents of a mutable BitSet (mutable rather than immutable for performance) that I posted as an answer to another question:
@mfa 提到使用 Eratosthenes -SoE的筛子，@Luigi Plinge 提到这应该使用功能代码来完成，所以@netzwerg 发布了一个非 SoE 版本；在这里，我使用完全不可变的状态发布了 SoE 的“几乎”功能版本，除了我作为另一个问题的答案发布的可变 BitSet（可变而不是不可变的性能）的内容：
object SoE {
def makeSoE_Primes(top: Int): Iterator[Int] = {
val topndx = (top - 3) / 2
val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
def cullp(i: Int) = {
import scala.annotation.tailrec; val p = i + i + 3
@tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
cull((p * p - 3) >>> 1)
}
(0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
}
}
回答by madooc
How about this.
这个怎么样。
def getPrimeUnder(n: Int) = {
require(n >= 2)
val ol = 3 to n by 2 toList // oddList
def pn(ol: List[Int], pl: List[Int]): List[Int] = ol match {
case Nil => pl
case _ if pl.exists(ol.head % _ == 0) => pn(ol.tail, pl)
case _ => pn(ol.tail, ol.head :: pl)
}
pn(ol, List(2)).reverse
}
It's pretty fast for me, in my mac, to get all prime under 100k, its take around 2.5 sec.
对我来说，在我的 mac 中，将所有质数都降到 100k 以下非常快，大约需要 2.5 秒。
回答by mfa
A sieve method is your best bet for small lists of numbers (up to 10-100 million or so). see: Sieve of Eratosthenes
筛选方法是小数字列表（最多 10-1 亿左右）的最佳选择。参见：埃拉托色尼筛
Even if you want to find much larger numbers, you can use the list you generate with this method as divisors for testing numbers up to n^2, where n is the limit of your list.
即使您想找到更大的数字，您也可以使用通过此方法生成的列表作为除数来测试最大为 n^2 的数字，其中 n 是列表的限制。
回答by Justice O.
A scalar fp approach
标量 fp 方法
// returns the list of primes below `number`
def primes(number: Int): List[Int] = {
number match {
case a
if (a <= 3) => (1 to a).toList
case x => (1 to x - 1).filter(b => isPrime(b)).toList
}
}
// checks if a number is prime
def isPrime(number: Int): Boolean = {
number match {
case 1 => true
case x => Nil == {
2 to math.sqrt(number).toInt filter(y => x % y == 0)
}
}
}
回答by Navin Gelot
def primeNumber(range: Int): Unit ={
val primeNumbers: immutable.IndexedSeq[AnyVal] =
for (number :Int <- 2 to range) yield {
val isPrime = !Range(2, Math.sqrt(number).toInt).exists(x => number % x == 0)
if(isPrime) number
}
for(prime <- primeNumbers) println(prime)
}
回答by Noel Yap
object Primes {
private lazy val notDivisibleBy2: Stream[Long] = 3L #:: notDivisibleBy2.map(_ + 2)
private lazy val notDivisibleBy2Or3: Stream[Long] = notDivisibleBy2
.grouped(3)
.map(_.slice(1, 3))
.flatten
.toStream
private lazy val notDivisibleBy2Or3Or5: Stream[Long] = notDivisibleBy2Or3
.grouped(10)
.map { g =>
g.slice(1, 7) ++ g.slice(8, 10)
}
.flatten
.toStream
lazy val primes: Stream[Long] = 2L #::
notDivisibleBy2.head #::
notDivisibleBy2Or3.head #::
notDivisibleBy2Or3Or5.filter { i =>
i < 49 || primes.takeWhile(_ <= Math.sqrt(i).toLong).forall(i % _ != 0)
}
def apply(n: Long): Stream[Long] = primes.takeWhile(_ <= n)
def getPrimeUnder(n: Long): Long = Primes(n).last
}
