Project Euler 010 – F#

Problem

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

Find the sum of all the primes below two million.

Code

let isPrime n = 

    if n = 2 then true

    else if n % 2 = 0 then false

    else

        let m = int (sqrt (float n))

        [3..2..m] |> List.exists (fun elem-> n % elem = 0) |> not

let primeList n =

    [2..n] 

    |> List.filter isPrime

let littlePrimes  = primeList (int (sqrt 2000000.0))

let isPrimeFromList n (primes : list<int>) = 

    primes 

    |> List.exists (fun elem-> n % int(elem) = 0) 

    |> not

let remainingPrimes = [int(sqrt(2000000.0)) .. 2000000] 

                      |> List.filter(fun elem -> isPrimeFromList elem littlePrimes)

printfn "%A" (bigint(littlePrimes |> List.sum)

               + (remainingPrimes |> List.map(fun elem -> bigint(elem)) |> List.sum))

Discussion

This probably needs a little explaining.  I broke the problem into two parts:

1. Primes less than the square root of 2,000,000 (~1414)
2. Primes greater than 1414 and less than 2,000,000

I chose to solve the problem this way because determining the primes from 2 – 1414 is pretty quick even using a naïve brute force attack.  Once I have those primes, I can use them as factors to determine the remaining primes.

All told, this code takes about 1.3 seconds to run on my machine.

Love it?  Hate it?  Leave a comment.  You can also find me at http://twitter.com/eulersolutions.