素因数分解

Factorization.scala

import scala.annotation._

object Factorization {

  /** 素数 */
  type Prime = Long
  /** 指数 */
  type Exponent = Int
  
  val primes: Stream[Prime] = 2 #:: sieve(3)

  private def sieve(n: Long): Stream[Prime] =
    if (primes.takeWhile(p => p * p <= n).exists(n % _ == 0)) sieve(n + 2)
    else n #:: sieve(n + 2)

  def factorize(n: Long): Seq[(Prime, Exponent)] = factorize(n, primes)

  private def factorize(n: Long, ps: Stream[Prime]): List[(Prime, Exponent)] = {
    if (n <= 1) return Nil
    val head #:: tail = ps
    if (head * head > n) return List((n, 1))
    val (exponent, quot) = calculateExponent(n, head, 0)
    if (exponent == 0) factorize(quot, tail)
    else (head, exponent) :: factorize(quot, tail)
  }
  
  /**
   *  n を割り切ることができる prime の最大の指数と、
   * 割り切った時の商を (指数, 商) として返す
   */
  @tailrec
  private def calculateExponent(n: Long, prime: Prime, exponent: Exponent): (Exponent, Long) =
    if (n % prime != 0) (exponent, n)
    else calculateExponent(n / prime, prime, exponent + 1)

  def main(args: Array[String]) {
    val n = args(0).toLong
    println(n)
    val start = System.currentTimeMillis
    val exp = factorize(n).map { case (p, o) => p + "^" + o }.mkString(" * ")
    println(exp)
    println(System.currentTimeMillis - start)
  }
}