ScalaでProject Euler（89）

Problem 58

Problem 28の対角線上を辿るコードをそのまま使えます。あとは適当に素数判定するだけです。
10%で3.4s、9%で26sでした。かなり遅い素数判定ですが。

import scala.testing.Benchmark

def is_prime(n :Long) =
    Iterator.from(2).takeWhile(p => p.toLong * p <= n).forall(p => n % p != 0)

def step(s :(Int,Int,Long)) = s match {
    case (x, y, n) if x > 0 && y < 0 => (-x, y, n + x * 2)
    case (x, y, n) if x < 0 && y < 0 => (x, -y, n - x * 2)
    case (x, y, n) if x < 0          => (-x, y, n - x * 2)
    case (x, y, n)                   => (x + 1, -y - 1, n + x * 2 + 2)
}

def next(s :(Int,Int,Int,Iterator[Long])) = {
    val (len, num_p, num, it) = s
    val np = it.take(4).count(is_prime)
    (len + 2, num_p + np, num + 4, it)
}

def solve() = {
    val N = 9
    val it = Iterator.iterate((0, 0, 1L))(step).map(_._3).drop(1)
    println (Iterator.iterate((1, 0, 1, it))(next).drop(1).
            filter(s => s._2 * 100 < s._3 * N).map(_._1).next)
}

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

println (Test.runBenchmark(1))