Project Euler Problem #10

  • Article

Sum of primes below two-million.

Easy problem, but way too slow (taking several minutes) with the naïve prime number generator from problem 7. This new version is 10x faster, based on this paper:https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf (still not implementing the 'wheel' though; probably another 3x improvement)

let primes =
    let rec sieve i c = seq {
        match Map.tryFind i c with
        | None -> yield i
                  yield! sieve (i + 1L) (Map.add (i * i) [i] c)
        | Some(f) -> yield! sieve (i + 1L) (List.fold (fun c p –>
            Map.add (i + p) (match Map.tryFind (i + p) c with
                                None -> [p] | Some(f) -> p :: f) c)
                                (Map.remove i c) f) }
    sieve 2L Map.empty
primes |> Seq.takeWhile ((>=) 2000000L) |> Seq.sum