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.

Solution

(*

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

 

Find the sum of all the primes below two million.

*)

 

open System

 

let start = DateTime.Now

 

let isPrime n =

    let m = bigint (sqrt (float n))

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

 

let primeList n =

    [2I..n]

    |> List.filter isPrime

 

 

let primes  = primeList (bigint (sqrt 2000000.0))

 

let isPrimeFromList n primes =

    primes |> List.exists (fun elem-> n % elem = 0I) |> not

 

let remainingPrimes = [bigint(sqrt(2000000.0)) .. 2000000I] |> List.filter(fun elem -> isPrimeFromList elem primes)

 

printfn "%A" ((primes |> List.sum) + (remainingPrimes |> List.sum))

 

let elapsed = DateTime.Now – start

printfn "%A" elapsed

 

Discussion

I ran into some difficult with this problem as my previous prime determination algorithms were recursive and ended up overflowing the stack.  This solution takes just under 20 seconds on my laptop.  I broke the prime determination into two sections. 

The first is a really naïve solution that checks all of the numbers up to square root of 2 million.  This will give me all of the primes I need to test for primality on the remaining primes.

The second is then a prime test that uses the list of primes to determine the primality.  It’s not real fast, but it gets the job done.

Please, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).