使用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筛选的功能实现,如Odersky的"Scala中的功能编程原则"Coursera课程中所示:

  // Sieving integral numbers
  def sieve(s: Stream[Int]): Stream[Int] = {
    s.head #:: sieve(s.tail.filter(_ % s.head != 0))
  }

  // All primes as a lazy sequence
  val primes = sieve(Stream.from(2))

  // Dumping the first five primes
  print(primes.take(5).toList) // List(2, 3, 5, 7, 11)

Answer 2

这种风格对我来说很好看.尽管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)

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

Answer 3

正如schmmd提到的那样,你希望它是尾递归的,你也希望它是懒惰的.幸运的是,有一个完美的数据结构:Stream.

这是一个非常有效的主要计算器,实现为a Stream,只需一些优化:

object Prime {
  def is(i: Long): Boolean =
    if (i == 2) true
    else if ((i & 1) == 0) false // efficient div by 2
    else prime(i)

  def primes: Stream[Long] = 2 #:: prime3

  private val prime3: Stream[Long] = {
    @annotation.tailrec
    def nextPrime(i: Long): Long =
      if (prime(i)) i else nextPrime(i + 2) // tail

    def next(i: Long): Stream[Long] =
      i #:: next(nextPrime(i + 2))

    3 #:: next(5)

  }

    // assumes not even, check evenness before calling - perf note: must pass partially applied >= method
  def prime(i: Long): Boolean =
    prime3 takeWhile (math.sqrt(i).>= _) forall { i % _ != 0 }
}

Prime.is是主要检查谓词,并Prime.primes返回Stream所有素数中的一个.prime3是计算流的位置,使用素数谓词来检查小于平方根的所有素数除数i.