Project Euler Problem 10 in F#

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.

See all Project Euler problems solutions.

kick it on DotNetKicks.com

Shout it

This entry was posted in .NET, F# and tagged , , . Bookmark the permalink.