Project Euler Problem 10 asks a very simple question, again dealing with prime numbers:

Calculate the sum of all the primes below two million.

I am giving here two solutions, using two different approaches:

#light open System.Collections.Generic // SOLUTION 1: TRIAL DIVISION let is_prime (x:int64) = let rec check i = double i > sqrt (double x) || (x % i <> 0L && check (i + 1L)) check 2L let trial_division (n:int64) = seq { for i in 2L .. n do if is_prime i then yield i } |> Seq.takeWhile (fun x -> x < n) |> Seq.sum // SOLUTION 2: USE THE SIEVE let sieve (n:int64) = let candidatePrimes = new Dictionary<int64, bool>() for i in 2L .. n do candidatePrimes.Add(i, true) for i in 2L .. n/2L do if candidatePrimes.[i] = true then let mutable j = i while (j + i <= n) do j <- j + i candidatePrimes.[j] <- false seq { for i in 2L .. n do if candidatePrimes.[i] = true then yield i } |> Seq.sum

- The first solution uses trial division to create a sequence of all primes under a certain threshold. It's the easiest method to understand.
- The second solution is a naive implementation of the Sieve of Erathostenes. I first mark all the numbers as candidate primes; then starting from 2 I mark off all the multiples, move to the next candidate prime, until only primes are left (you can refer to the Wikipedia article for all the details).
As you can see, this second solution looks has a more imperative feel to it, using mutable data (a dictionary and a counter). Based on my tests for numbers from 1 to 10 millions, it's at least twice as fast as the trial division method.

Pingback: DotNetShoutout

Pingback: Rick Minerich's Development Wonderland : F# Discoveries This Week 09/17/2010