Monday, May 10, 2010

Problem 10: Find the sum of all the primes below two million.

This problem is a variation on Problem 7 allowing us to reuse isPrime and modify nthPrime to build a list of primes up to a max.

//problem 10
let problem10a =
    let primes max = 
        let rec primes i plist =
            if i > max then plist
            elif i |> isPrime then primes (i+2) (i::plist)
            else primes (i+2) plist
        primes 3 [2] //start at 3, and with a list containing our only even prime
        
    primes 1999999 |> List.sumBy int64  //convert to int64 to avoid overflow

Another solution using a sequence expression is even nicer though,

let problem10b =
    (seq { for i in 3..2..1999999 do if i |> isPrime then yield i} //odd primes
    |> Seq.sumBy int64) + 2L //dont forget 2

No comments:

Post a Comment