Prime factorization using recursion Scala

user_13300645 0
Viewed 839

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.

prime-factoring recursion scala
2 Answers

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.

user_76626700

Well, you can debug your code, and see that once you passed a number, you won't print it again.

In order to print all primes, you need to divide in the prime you found, and start over with the divided number. Please consider the following implantation for 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)
 }
}

Now you get the output: 2, 2, 2, 5, 5. Code run can be found at Scastie.

user_23592270
Related