ScalaでProject Euler（38）

Problem 21

エラトステネスのふるい的に約数の和を求めるだけですね。

import scala.testing.Benchmark

def sum_pows(n :Int, e :Int) =
    (1 to e).foldLeft(1)((x, y) => x * n + 1)

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)
    
    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 sum_divs(n :Int) :Int =
        if(n == 1)
            1
        else {
            val p = a(n)
            val (e, m) = div_pow(n, p)
            sum_pows(p, e) * sum_divs(m)
        }
    
    def sum_divisors(n :Int) = sum_divs(n) - n
    
    def sum_amicable(n :Int) = {
        val m = sum_divisors(n)
        if(m < n && n == sum_divisors(m))
            n + m
        else
            0
    }
    
    println (Iterator.range(2, N).map(sum_amicable).sum)
}

val N = 1e6.toInt
println (Test.runBenchmark(5))