使用Scala查找质数。帮我改善

Question

我写了这段代码来查找小于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)

但是，我感觉到了findPrime函数，尤其是这一部分：

case _ => {
    val primeList = findPrime(i-1)
    if(isPrime(i, primeList)) i :: primeList else primeList
}

不太符合功能风格。

我仍在学习函数式编程。谁能帮助我改善此代码，使其更具功能。

非常感谢。

Answer 1

样式在我看来不错。尽管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)

这个解决方案并不漂亮-
它是使您的解决方案适用于大参数的更多细节。由于列表是向后构建的，因此可以利用快速添加的内容，因此需要将列表反转。作为替代方案，你可以使用一个Array，Vector或ListBuffer对结果追加。Array但是，使用时，您需要估计要为其分配多少内存。幸运的是，我们知道它pi(n)大约等于，n / ln(n)因此您可以选择一个合理的尺寸。 Array并且ListBuffer也是一个可变的数据类型，它又来了您的功能性风格的愿望。

更新：为了从Eratosthenes筛中获得良好的性能，我认为您需要将数据存储在本机数组中，这也违反了您对函数式编程风格的渴望。不过可能会有一个创造性的功能实现！

更新：哎呀！错过了！ 如果您只用质数除以要测试的数的平方根作为除数， 这种方法也很好 用
！我错过了这一点，不幸的是，调整解决方案来做到这一点并不容易，因为我要向后存储素数。

更新：这是一个非常不实用的解决方案，至少只能检查平方根。

rnative，你可以使用一个Array，Vector或ListBuffer对结果追加。Array但是，使用时，您需要估计要为其分配多少内存。幸运的是，我们知道它pi(n)大约等于，n / ln(n)因此您可以选择一个合理的尺寸。 Array并且ListBuffer也是一个可变的数据类型，它又来了您的功能性风格的愿望。

更新：为了从Eratosthenes筛中获得良好的性能，我认为您需要将数据存储在本机数组中，这也违反了您对函数式编程风格的渴望。不过可能会有一个创造性的功能实现！

更新：哎呀！错过了！ 如果您只用质数除以要测试的数的平方根作为除数， 这种方法也很好 用
！我错过了这一点，不幸的是，调整解决方案来做到这一点并不容易，因为我要向后存储素数。

更新：这是一个非常不实用的解决方案，至少只能检查平方根。

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)

或者我可以将Vectors与我的原始方法结合使用。 Vectors可能不是最佳解决方案，因为即使分期偿还O（1），他们也没有禁食的O（1）。