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

问题描述

我写这篇code找到素数小于给定数量我在Scala中。

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
}

倒不在功能风格。

is not quite in the functional style.

我还在学习函数式编程。任何人都可以请帮我改善这种code，使其更加实用。

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

非常感谢。

推荐答案

的样式看起来好像没什么问题。虽然埃拉托色尼的筛是一种非常有效的方式找到素数，你的做法效果很好过，因为你只是在测试的分工对已知的素数。您需要但要小心 - 你的递归函数不是尾递归。尾递归函数不修改递归调用的结果 - 在你的榜样，你prePEND递归调用的结果。这意味着，你将有一个长调用堆栈等findPrime不会为大我的工作。这里是一个尾递归的解决方案。

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)

这个解决方案不是prettier - 它更多的是细节，让您的解决方案，以工作的大争论。因为该列表建立向后利用快速prepends，列表需要被反转。作为替代方案，你可以使用阵列，向量或 ListBuffer 追加结果。随着阵列，但是，您将需要估计有多少内存分配给它。幸运的是，我们知道， PI（N）约等于 N / LN（N）所以你可以选择一个合理的尺寸。 阵列和 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.

更新：获得良好表现出来的埃拉托色尼筛我认为你需要将数据存储在本地阵列，这也违背了你的愿望风格函数式编程。有可能是一个创造性的功能的实现，但！

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.

rnative，你可以使用阵列，向量或 ListBuffer 追加结果。随着阵列，但是，您将需要估计有多少内存分配给它。幸运的是，我们知道， PI（N）约等于 N / LN（N）所以你可以选择一个合理的尺寸。 阵列和 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.

更新：获得良好表现出来的埃拉托色尼筛我认为你需要将数据存储在本地阵列，这也违背了你的愿望风格函数式编程。有可能是一个创造性的功能的实现，但！

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)

我还可以使用向量 s的我原来的做法。 向量是可能不是最好的解决方案，因为他们没有禁食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屋！