素因数分解

primeDec.scala

//scalaっぽい素因数分解
import scala.annotation.tailrec

object PrimeTest extends App {
  def primeDec(n: Int) = {
    @tailrec
    def r(in: Int, plist: List[Int], result: List[Int] = List()): List[Int] = {
      plist match {
        case x :: xs if in % x == 0 => r(in / x, plist, x :: result)
        case x :: xs if in % x != 0 => r(in, xs, result)
        case _ => result
      }
    }
    val plist = 2 to n filter (BigInt(_).isProbablePrime(64) == true)
    r(n, plist.toList).reverse;
  }
  assert(primeDec(2) == List(2))
  assert(primeDec(3) == List(3))
  assert(primeDec(4) == List(2, 2))
  assert(primeDec(30) == List(2, 3, 5))
  assert(primeDec(100) == List(2, 2, 5, 5))
}

primeDec2.scala

//普通の素因数分解
import scala.annotation.tailrec

object PrimeTest2 extends App {
  def primeDec(n: Int) = {
    @tailrec
    def r(in: Int, c: Int = 2, result: List[Int] = List()): List[Int] = {
      if (in < c) {
        result
      } else if (in % c == 0) {
        r(in / c, c, c :: result)
      } else {
        r(in, c + 1, result)
      }
    }
    r(n).reverse;
  }
  assert(primeDec(2) == List(2))
  assert(primeDec(3) == List(3))
  assert(primeDec(4) == List(2, 2))
  assert(primeDec(30) == List(2, 3, 5))
  assert(primeDec(100) == List(2, 2, 5, 5))
}