ScalaでProject Euler（46）

Problem 27

まず、bは3以上の奇数で、aも奇数であることがわかります。2以外の素数についても同様の考察ができてそれはそれで面白いのですが、そんなことをしなくても素数判定をメモ化するだけで十分速くなります。

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

def solve() = {
    val N = 1000
    val memo = Map[Int,Boolean]()
    
    def is_prime(n :Int) =
        if(n < 2)
            false
        else if(memo.contains(n))
            memo(n)
        else {
            val b = Iterator.from(2).takeWhile(m => m * m <= n).
                                                forall(n % _ != 0)
            memo(n) = b
            b
        }
    
    def len(a :Int, b :Int) :Int =
        Iterator.from(0).map(n => n * (n + a) + b).takeWhile(is_prime).size
    
    val it = Iterator.range(-N + 1, N, 2).flatMap(
                    a => Iterator.range(3, N, 2).map((a, _)))
    val (n, (a, b)) = it.map(x => (len(x._1, x._2), x)).max
    println (a * b)
}

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

println (Test.runBenchmark(10))