Sieve of Eratosthenes in F#

If you don’t know what the Sieve of Eratosthenes is, don’t worry because a few days ago neither did I. But in short it is a very simple way to calculate prime numbers. Essentially you loop through all integers and keep a list of numbers which are known to be composite. If you encounter a number which isn’t in your list, then it is prime. At which point you add all multiples of that prime number to your list, since you know they are composite.

There is definitely room for improvement in my implementation, it’s a good example of using F# Computation Expressions to generate a sequence of prime numbers.

#light

// Reference System.Core in the v3.5 framework for 'HashSet'
#r @"C:\Windows\assembly\GAC_MSIL\System.Core\3.5.0.0__b77a5c561934e089\System.Core.dll"

open System
open System.Collections.Generic

let primesUnderOneMillion =
    seq {
        // First prime
        yield 2

        let knownComposites = new HashSet<int>()
       
        // Loop through all odd numbers; evens can't be prime
        for i in 3 .. 2 .. int 1E6 do

            // Check if its in our list, if not, its prime
            let found = knownComposites.Contains(i)
            if not found then
yield i

            // Add all multiples of i to our sieve, starting
// at i and irecementing by i.
            do for j in i .. i .. int 1E6 do
                   knownComposites.Add(j) |> ignore
    }
   
printfn "The first 50 primes:"
Seq.iter (fun p -> printf "\t%d" p) (Seq.take 50 primesUnderOneMillion)

Console.ReadKey(true)

Comments

• Anonymous
  April 29, 2008
  PingBack from http://microsoftnews.askpcdoc.com/f/sieve-of-eratosthenes-in-f

• Anonymous
  May 30, 2008
  Last Tuesday I gave a talk to the .NET Developers Association entitled Language Oriented Programming

• Anonymous
  September 10, 2008
  look i like wat your doin but ive been through 55 google pages trying to find why he created it for my proect