ScalaでProject Euler（115）

Problem 77

前問とほとんど同じです。再帰に持ち込んでメモ化です。

import scala.collection.mutable.Map
import scala.testing.Benchmark

object DivIntegerByPrime {
    val primes :Stream[Int] = 2 #:: Stream.from(3).filter(is_prime)
    def is_prime(n :Int) :Boolean =
        primes.takeWhile(p => p * p <= n).forall(p => n % p != 0)
    
    val memo = Map[(Int,Int),Long]()
    
    def apply(n :Int) :Long = f(n, n) - (if(is_prime(n)) 1 else 0)
    def clear() = memo.clear()
    
    private def f(n :Int, m :Int) :Long =
        if(n == 0)
            1
        else if(memo.contains((n, m)))
            memo((n,m))
        else {
            val s = primes.takeWhile(m >=).map(p => f(n - p, p.min(n - p))).sum
            memo((n,m)) = s
            s
        }
}

def solve() = {
    val N = 5000
    println (Iterator.from(2).map(n => (n, DivIntegerByPrime(n))).
                                        filter(x => x._2 > N).next._1)
    DivIntegerByPrime.clear()
}

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

println (Test.runBenchmark(10))