ScalaでProject Euler（76）

Problem 46

範囲がわからないと計算しにくい問題ですが、こういうときは範囲を適当に決めて、その中に解が無ければ範囲を2倍にする、という操作を繰り返しますのが簡単です。本当は計算量の増加具合で範囲の広げ方を決めるべきなのですが、2倍でもよいでしょう。

def solve(N :Int) = {
    val a = new Array[Boolean](N + 1)
    for(k <- 2 to N) a(k) = true
    for(p <- 2 to N if a(p); k <- p * 2 to N by p)
        a(k) = false
    
    val ps = List.range(2, N + 1).filter(k => a(k))
    
    for(p <- ps;
        k <- Iterator.from(1).takeWhile(k => p + 2 * k * k <= N))
            a(p + 2 * k * k) = true
    
    Iterator.range(3, N + 1, 2).filter(n => !a(n))
}

val it_N = Iterator.iterate(1000)(2 *)
println (it_N.flatMap(N => solve(N)).next)