Prime factorization using recursion Scala

Question

I am trying to write a recursive function in Scala that takes a positive integer and prints out its prime factors. For example, 200 = 2, 2, 2, 5, 5. This is the code I have written.

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

My code outputs 2,5, .

How can I make this so that the code works correctly and outputs 2,2,2,5,5,. I tried using a loop with this statement n = n / i, but Scala returns an error saying that reassignment to val can't be done.

Answer 1

A clean version of this algorithm might look like this:

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

Use mkString(", ") to convert the result to a String if required.

Note that there is no need to check that the divisor is prime since any non-prime divisor will have smaller prime factors which will have already been removed.