ScalaでProject Euler（12）

Problem 5

この問題は最小公倍数を求めるだけですが、Intの範囲で収めようとするとちょっとだけ工夫が必要です。

reduce系メソッド

最小公倍数を次々と求めるにはreduceLeftを使います。これはPythonのreduceとだいたい同じです。違うところは初期値が取れないところくらいでしょうか。簡単な例は和を取る処理です。

println ((1 to 4).reduceLeft(_ + _))    // 10

reduceRightもあります。

println ((1 to 4).reduceRight(_ + _))   // 10

結果は同じですが、処理が違います。reduceLeftは、

((1 + 2) + 3) + 4

reduceRightは

1 + (2 + (3 + 4))

です。つまり再帰です。再帰だから深さに限界があるはずです。

println ((1 to 1e6.toInt).reduceRight(_ - _))   // -500000

えっと、100万でも答え出ますね。Haskellでも30万くらいだったと思いましたが。

println ((1 to 1e7.toInt).reduceRight(_ - _))

java.lang.OutOfMemoryError: Java heap space

これだとさすがに落ちます。300MB以上メモリを食ってました。reduceLeftなら、

println ((1 to 1e7.toInt).reduceLeft(-_ + _))   // 5000000

これなら問題無いです。それでも50MB以上食ってました。
今回の問題は、

def gcd(m :Int, n :Int) :Int =
    if(n == 0) m else gcd(n, m % n)

def lcm(m :Int, n :Int) :Int =
    m * (n / gcd(m, n))

val N = 20
println ((1 to N).reduceLeft(lcm))