使用 Scala 查找素数.帮助我改进 [英] Find prime numbers using Scala. Help me to improve

问题描述

我编写这段代码是为了在 Scala 中找到小于给定数 i 的素数.

I wrote this code to find the prime numbers less than the given number i in scala.

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 函数有一种感觉，尤其是这部分:

But, I got a feeling the findPrime function, especially this part:

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

不太符合函数式风格.

我仍在学习函数式编程.任何人都可以帮助我改进此代码以使其更实用.

I am still learning functional programming. Can anyone please help me improve this code to make it more functional.

非常感谢.

推荐答案

我觉得这个风格不错.尽管 Eratosthenes 筛法是一种非常有效的查找素数的方法，但您的方法也很有效，因为您只是在测试与已知素数的除法.但是，您需要注意——您的递归函数不是尾递归的.尾递归函数不会修改递归调用的结果——在您的示例中，您将递归调用的结果放在前面.这意味着您将有一个很长的调用堆栈，因此 findPrime 不适用于大 i.这是一个尾递归解决方案.

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.

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 也是可变数据类型，再次满足你对函数式风格的渴望.

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, Vector or a ListBuffer to 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. Array and ListBuffer are also a mutable data types, which goes again your desire for functional style.

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

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!

更新:哎呀！错过了！这种方法也很有效如果您只除以小于您要测试的数字的平方根的素数！我错过了这一点，不幸的是，调整我的解决方案来做到这一点并不容易，因为我正在向后存储质数.

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.

本地，您可以使用 Array、Vector 或 ListBuffer 来附加结果.但是，对于 Array，您需要估计要为其分配多少内存.幸运的是，我们知道 pi(n) 大约等于 n/ln(n) 所以你可以选择一个合理的大小.Array 和 ListBuffer 也是可变数据类型，再次满足你对函数式风格的渴望.

rnative, you could use an Array, Vector or a ListBuffer to 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. Array and ListBuffer are also a mutable data types, which goes again your desire for functional style.

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

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!

更新:哎呀！错过了！这种方法也很有效如果您只除以小于您要测试的数字的平方根的素数！我错过了这一点，不幸的是，调整我的解决方案来做到这一点并不容易，因为我正在向后存储质数.

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)

或者我可以在我原来的方法中使用 Vectors.Vectors 可能不是最好的解决方案，因为它们没有禁食 O(1)，即使它摊销了 O(1).

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).

这篇关于使用 Scala 查找素数.帮助我改进的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！