CODEWITHSUNDEEP
scala
mpprdev
mpprdev

Reputation: 1283

Generate prime factors of a number in Scala

How can I generate the factors of an integer in Scala? Here's my take 1:

def factorize(x: Int): List[Int] = {

  def foo(x: Int, a: Int): List[Int] = {

    if (a > Math.pow(x, 0.5))
      return List(x)

    x % a match {
      case 0 => a :: foo(x / a, a)
      case _ => foo(x, a + 1)
    }
  }

  foo(x, 2)
}

factorize(360) // List(2, 2, 2, 3, 3, 5)

Take 2 based on comments from @SpiderPig and @seth-tisue

def factorize(x: Int): List[Int] = {
  def foo(x: Int, a: Int): List[Int] = {
    (a*a < x, x % a) match {
        case (true, 0) => a :: foo(x/a, a)
        case (true, _) => foo(x, a+1)
        case (false, _) => List(x)
      }
  }
  foo(x, 2)
}

Upvotes: 6

Views: 4973

Answers (2)

dk14
dk14

Reputation: 22374

Just little improvement of "Take 2" from the question:

def factorize(x: Int): List[Int] = {
  def foo(x: Int, a: Int): List[Int] = x % a match {
     case _ if a * a > x  => List(x)
     case 0 => a :: foo(x / a, a)
     case _ => foo(x, a + 1)
  }
  foo(x, 2)
}

Also, the following method may be a little faster (no x % a calculation in the last iteration):

def factorize(x: Int): List[Int] = {
  def foo(x: Int, a: Int): List[Int] = if (a * a > x) List(x) else
    x % a match {
      case 0 => a :: foo(x / a, a)
      case _ => foo(x, a + 1)
    }
  foo(x, 2)
}

Upvotes: 0

LRLucena
LRLucena

Reputation: 1705

A tail recursive solution:

def factorize(x: Int): List[Int] = {
  @tailrec
  def foo(x: Int, a: Int = 2, list: List[Int] = Nil): List[Int] = a*a > x match {
    case false if x % a == 0 => foo(x / a, a    , a :: list)
    case false               => foo(x    , a + 1, list)
    case true                => x :: list
  }
  foo(x)
}

Upvotes: 10

Related Questions