tags:

## 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.