Project Euler 010 – F#
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
let isPrime n =
if n = 2 then true
else if n % 2 = 0 then false
let m = int (sqrt (float n))
[3..2..m] |> List.exists (fun elem-> n % elem = 0) |> not
let primeList n =
|> List.filter isPrime
let littlePrimes = primeList (int (sqrt 2000000.0))
let isPrimeFromList n (primes : list<int>) =
|> List.exists (fun elem-> n % int(elem) = 0)
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))
This probably needs a little explaining. I broke the problem into two parts:
- Primes less than the square root of 2,000,000 (~1414)
- 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.