Project Euler Problem 10 in F#

1 minute read

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:

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

Updated:

Leave a Comment