获取N的素数列表

Question

我正在尝试编写一个函数，该函数接受一个I​​nt并返回直到该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”的映射函数，并为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。

Answer 2

所述的实施埃拉托塞尼的筛用于高效地查找素数达到给定值的算法N包括以下内容，（固定和改进此 SO回答），

implicit class Sieve(val N: Int) extends AnyVal {
  def primesUpTo() = {
    val isPrime = collection.mutable.BitSet(2 to N: _*) -- (4 to N by 2)
    for (p <- 2 +: (3 to Math.sqrt(N).toInt by 2) if isPrime(p)) {
      isPrime --= p*p to N by p
    }
    isPrime.toImmutable
  }
} 

因此

10.primesUpTo.toList
res: List(2, 3, 5, 7)

11.primesUpTo.toList
res: List(2, 3, 5, 7, 11)

注意使用Scala查找质数。帮助我改进其他想法和讨论。