scala - 获取 N 的素数列表

Question

我正在尝试编写一个函数，它接受一个 Int 并返回直到并包括该 Int 的所有素数。

例如“8 的素数列表”= List(3,5,7)

这是我到目前为止:

  def isPrime(i: Int): Boolean = {
    if (i <= 1)
      false
    else if (i == 2)
      true
    else
      !(2 to (i - 1)).exists(x => i % x == 0)
  }                                               //> isPrime: (i: Int)Boolean

    def getListOfPrimesToN(n : Int) = {

    }

对于我计划使用的函数 getListOfPrimesToN
1. 创建一个大小为 n 的列表“l”，并用从 0 到 n 的元素填充它。
2.调用“l”的map函数，对List中的每个元素调用isPrime。

如何创建元素 1 到 N 的列表？

返回所有质数的任何替代解决方案，包括 Int N 欢迎。

Answer 1

您可以使用无限流来解决此问题。如果你有一个包含所有素数的流 primes ，你可以只说 primes.takeWhile(_ <= n) 来获取包含 n 的素数。

要获得所有质数，您从第一个质数 2 开始的所有数字流开始。然后您可以跳过所有偶数，因为它们绝对不是素数。然后你可以跳过所有其他不是素数的数字。

val primes = 2 #:: Stream.from(3,2).filter(isPrime)

现在你只需要 isPrime 来检查给定的数字是否是素数。如果一个数不能被任何较小的素数整除，则该数为素数。我们实际上只需要考虑平方不大于数字的素数(因为，合数的最小素数因子不能大于它的平方根)。

def isPrime(n: Int): Boolean =
  primes.takeWhile(p => p*p <= n).forall(n % _ != 0)

在 REPL 中检查:

scala> primes.takeWhile(_ <= 8).toList
res0: List[Int] = List(2, 3, 5, 7)

警告:这仅适用于小于 Integer.MAX_VALUE 的正数。