gistfile1.ml

#light

open System
open System.Collections.Generic
open Microsoft.FSharp.Math

let memoize (f:'a -> 'b) =
    let t = new Dictionary<'a, 'b>()
    fun n -> if t.ContainsKey(n) then t.[n]
             else let res = f n
                  t.Add(n, res)
                  res

let ceilSqrt (x:int64) =
  int64(float x |> sqrt |> ceil)

let rec primes (n:int64) =
  seq { 2L .. n }
  |> Seq.filter (fun x -> match x with
                          | _ when x <= 3L -> true
                          | _ when x % 2L = 0L -> false
                          | _ when x % 3L = 0L -> false
                          | _ -> match smallestPrimeFactor x with
                                 | Some(_) -> false
                                 | None -> true)
and smallestPrimeFactor =
  memoize(fun (x:int64) -> ceilSqrt x
                           |> primes
                           |> Seq.tryfind (fun y -> x % y = 0L))

do
    primes 2000000L
    |> Seq.sum
    |> printfn "Answer: %d"