Project Euler 010 – F#

4 04 2011

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

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: