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の後だと遅延評価なんでしょうか。