Project Eulerには再帰に持ち込めば簡単になる問題が多いです。5を分割することを考えます。まず5から4を取ります。残り1なのでその分割数を考えればよいです。次に5から3を取ります。残り2なので2の分割数を取ります。次に5から2を取ります。残り3の分割数を考えるのですが、最大は2という縛りがあります。1を取る場合も4を最大1で分割することを考えます。nを最大mで分割する場合の数をf(n, m)とすると、
f(5, 5) = f(0, 0) + f(1, 1) + f(2, 2) + f(3, 2) + f(4, 1)
となります。またf(0, m)は1と考えます。これでコードが書けるでしょう。68秒でした。
import scala.testing.Benchmark def num_divs(n :Int) :Int = { def f(n :Int, m :Int) :Int = if(n == 0) 1 else Iterator.range(1, m + 1).map(k => f(n - k, k.min(n - k))).sum f(n, n) - 1 } def solve() = { val N = 100 println (num_divs(N)) } object Test extends Benchmark { def run() = solve } println (Test.runBenchmark(1))