Project Euler Problem #10

Home/Uncategorized/Project Euler Problem #10

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #10.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Starting with the prime-generating code from my solution to problem #7:

open System
 
let dividesEvenly dividend divisor = int64(dividend % divisor) = 0L
let add x y = x + y
 
let rec isPrime x = 
    let limit = int(Math.Sqrt(float(x)))
    primes |> LazyList.to_seq |> Seq.takeWhile (fun i -> i <= limit) |> Seq.exists (dividesEvenly x) |> not
 
and primes =
    let nextPrime prevPrime =
        Seq.initInfinite (add (prevPrime + 1)) 
        |> Seq.filter isPrime
        |> Seq.hd
    let rec PrimesStartingFrom prime =
        LazyList.consf prime (fun () -> PrimesStartingFrom (nextPrime prime))
    LazyList.consf 2 (fun () -> PrimesStartingFrom 3)

All we need to do is add all of the primes below 2 million. Utilizing F#’s BigInt support we arrive at:

open Microsoft.FSharp.Math
 
let sum =
    primes
    |> Seq.takeWhile (fun i -> i < 2000000)
    |> Seq.map (fun i -> new bigint(i))
    |> Seq.fold (+) 0I

Leave a Comment