使用递归 Scala 进行质因数分解

Question

我正在尝试在 Scala 中编写一个递归函数，它接受一个正整数并打印出它的质因数。比如200 = 2, 2, 2, 5, 5。这是我写的代码。

println(calculatePrimeFactors(200,2))


def isPrime( x:Int ):Boolean = {
 def recIsP( n:Int, i:Int ) : Boolean = (i == n) || (n % i != 0) && recIsP(n, i + 1)
 recIsP(x,2)
}

def calculatePrimeFactors(n:Int,i:Int):String= {

 if (i==n) {
  ""
 }else if(isPrime(i) && n%i==0){
  i.toString + ", " + calculatePrimeFactors(n,i+1)
 }else{
  calculatePrimeFactors(n,i+1)
 }
}

我的代码输出 2,5, .

我怎样才能使代码正常工作并输出 2,2,2,5,5,. 我尝试将循环与此语句一起使用 n = n / i，但是 Scala returns 一个错误说重新分配给val 无法完成。

Answer 1

好吧，你可以调试你的代码，你会发现一旦你传递了一个数字，你就不会再打印了。

为了打印所有素数，您需要除以找到的素数，然后从除数开始。 calculatePrimeFactors 请考虑以下植入：

def calculatePrimeFactors(n:Int, i:Int):String= {

 if (i==n) {
  i.toString
 } else if(n%i==0) {
  i.toString + ", " + calculatePrimeFactors(n/i,i)
 } else {
  calculatePrimeFactors(n,i+1)
 }
}

现在您得到输出：2, 2, 2, 5, 5。代码运行可以在 Scastie.

找到

Answer 2

此算法的干净版本可能如下所示：

def calculatePrimeFactors(n: Int): List[Int] = {
  def loop(p: Int, rem: Int, res: List[Int]): List[Int] =
    if (rem % p == 0) {
      loop(p, rem / p, res :+ p)
    } else if (p > rem) {
      res
    } else {
      loop(p + 1, rem, res)
    }

  loop(2, n, Nil)
}

如果需要，使用 mkString(", ") 将结果转换为 String。

请注意，无需检查除数是否为质数，因为任何 non-prime 除数都将具有较小的质因数，这些因数已被删除。

使用递归 Scala 进行质因数分解

Prime factorization using recursion Scala

scala

recursion

prime-factoring