ScalaでProject Euler（49）

Problem 29

多倍長整数でなく素因数分解を使うのがふつうでしょうね。これならべき乗も簡単ですし。でも、N = 2000が限界でした。

import scala.testing.Benchmark

type Facts = List[(Int,Int)]

def pow(fs :Facts, e :Int) =
    fs.map(x => (x._1, x._2 * e))

def sieve(N :Int) = {
    val a = Array.range(0, N)
    for(p <- Iterator.from(2).takeWhile(n => n * n < N).filter(n => a(n) == n);
                    k <- Iterator.range(p * 2, N, p))
        a(k) = p
    a
}

object Test extends Benchmark {
    def run() = solve
}

def solve() = {
    val a = sieve(N + 1)
    
    def div_pow(n :Int, d :Int) :(Int,Int) =
        if(n % d != 0)
            (0, n)
        else {
            val (e, m) = div_pow(n / d, d)
            (e + 1, m)
        }
    
    def factorize(n :Int) :List[(Int,Int)] =
        if(n == 1)
            Nil
        else {
            val p = a(n)
            val (e, m) = div_pow(n, p)
            (p, e) :: factorize(m)
        }
    
    val it = Iterator.range(2, N + 1).map(factorize).flatMap(
                        a => Iterator.range(2, N + 1).map(pow(a, _)))
    println (it.toSet.size)
}

val N = 2000
println (Test.runBenchmark(5))