18 October, 2008

[Project Euler] Problem 10

Problem 10

 2000000以下の素数を得るには1415以下の素数が判れば良く、1415以下の素数を得るには37以下の素数が判れば良く、37以下の素数を知るには7以下の素数が2,3,5,7であることを知っていればOKである。
 という訳で、エラトステネスの篩を三段重ねにしてみた。

object P010 {
def main(args:Array[String]) {
val maxRange = 2000000
def primes(init:List[Int]):List[Int] = {
def min(a:Int, b:Int) = if (a<b) a else b
def sq(a:Int) = a*a
init ::: List.range(init.last+1, min(maxRange,sq(init.last))).filter{x => init.forall{x%_!=0}}
}
println(new java.util.Date())
val ps1 = List(2,3,5,7)
val ps2 = primes(ps1)
println(ps2.last)
val ps3 = primes(ps2)
println(ps3.last)
val ps4 = primes(ps3)
println(ps4.last)
println(ps4.foldLeft(0L)(_+_))
println(new java.util.Date())
}
}

No comments: