Scala流以查找特定间隔中的素数

Question

问题：

我需要创建一个Scala程序，它使用Stream类，并从区间[I，j]中找到第n个素数（而1<=I<j）。

更多信息：

我是Scala的新手，但我已经找到了各种关于如何使用Stream在Scala中找到素数的例子。他们都没有帮助我实现目标。

我似乎不明白如何使流成为区间[I，j]中的有限列表，以及如何从该区间中取第n个素数。

到目前为止我的代码：

def primeStream(args: Array[String], s: Stream[Int]): Stream[Int] =
        Stream.cons(s.head, primeStream(args,s.tail filter {_ % s.head != 0 }))
if (args(0).toInt < 1) {
        println("Entered parameter i does not meet requirements 1<=i<j (1<=" + args(0) + "<" + args(1) + ")")
        sys.exit(1)
} else if (args(1).toInt < args(0).toInt) {
        println("Entered parameter j does not meet requirements 1<=i<j (1<=" + args(0) + "<" + args(1) + ")")
        sys.exit(1)
}
val primes = primeStream(args,Stream.from(args(0).toInt)) // start from i element
primes take args(1).toInt foreach println //Take j elements

任何帮助都将不胜感激！

解决方案：

def primeStream(s: Stream[Int]): Stream[Int] =
        Stream.cons(s.head, primeStream(s.tail filter {_ % s.head != 0 }))
if (args(0).toInt < 1) {
        println("Entered parameter i does not meet requirements 1<=i<j (1<=" + args(0) + "<" + args(1) + ")")
        sys.exit(1)
} else if (args(1).toInt < args(0).toInt) {
        println("Entered parameter j does not meet requirements 1<=i<j (1<=" + args(0) + "<" + args(1) + ")")
        sys.exit(1)
} else if (args(0).toInt == 1) {
        println("1 is not a prime by definition!") 
        sys.exit(1)  // if args(0) is 1 then function hangs up - didn't come up with a better solution for this
}
val primes = primeStream(Stream.from(args(0).toInt)) // get primes starting from given parameter
println(primes.takeWhile( _ < args(1).toInt).take(args(2).toInt).last) // get n-th prime and print it out

Answer 1

您只需要在特定条件成立时让流生成值：

primes takeWhile(_ < j) take n foreach println

当然，您需要正确使用primeStream函数。

对于算法部分，你最好在stackoverflow上搜索：

• 在Scala中计算素数：这段代码是如何工作的

Answer 2

这是一个学习练习，还是在生产中需要？对于后者，我建议使用spire库中的spire.math.prime.stream。它使用的是Eratosthenes的分段流实现，这可能比您在短时间内提出的要好。它也使用任意精度的整数，所以它适用于大于2^64的数字。

scala> import spire.math._
import spire.math._
scala> prime.stream.drop(10).take(10).toArray
res16: Array[spire.math.SafeLong] = Array(31, 37, 41, 43, 47, 53, 59, 61, 67, 71)