Project Euler 10

http://projecteuler.net/index.php?section=problems&id=10

これはエラトステネスのふるいを使えという問題ですね。
新たに配列を導入します。

let a1 = [| 1; 2; 3 |]

範囲でも書けます。

let a2 = [| 1..3 |]

内包表記もあります。

let a3 = [| for i in 1..3 -> i * i |]

ここではtrueで全ての要素を初期化したいので内包表記も使えますが、ここではより簡単な次のような書き方をします。

let a4 = Array.create 3 true

インデックスへのアクセスは次のようです。

a4.[1] <- false

これでエラトステネスのふるいが書けます。

let sieve max_n = 
let sieve max_n = 
   let a = Array.create (max_n + 1) true
   a.[0] <- false
   a.[1] <- false
   for p in Seq.takeWhile (fun k -> k * k <= max_n)
            (Seq.filter (fun k -> a.[k])
            (Seq.initInfinite (fun k -> k))) do
      for k in p*2..p..max_n do
         a.[k] <- false
   
   List.filter (fun i -> a.[i]) [ 2..max_n ]

let N = int 2e6
let a = sieve (N - 1)
printfn "%d" (List.sum [ for n in a -> int64 n ])

sieveの中の素数を出すところでSequenceを使っているのはArrayにはtakeWhileがないからです。Arrayを使うと、

    let max_p = int (sqrt (float max_n))
    for p in Array.filter (fun k -> a.[k]) [| 2..max_p |] do
        for k in p*2..p..max_n do
            a.[k] <- false

少し遅いようですが、これでも正しく動作します。ということは、Array.filterは遅延評価しているってことですね。inの後だと遅延評価なんでしょうか。