[2009.03.01] The Sieve of Eratosthenes in F#

There are a number of Project Euler problems that involve prime numbers. I figured that before tackling those, I better learn how to generate prime numbers. As such, I have looked at the classic approach, called The Sieve of Eratosthenes. I did not follow that algorithm exactly as described on Wikipedia, but the solution is the same. The listing below shows how to use the code.

    1 #light

    2 #r "FSharp.PowerPack.dll"

    3 

    4 // The Sieve of Eratosthenes

    5 // You can get more information on the algorithm

    6 //  by searching http://en.wikipedia.org

    7 // I did not follow the exact method outlined, but

    8 //  the results are the same

    9 // My method removes odd and even numbers from the

   10 //  list in one go, and the remaining will be

   11 //  primes

   12 let rec sieveOfEra xs =

   13     match xs with

   14     | [] -> [] // if empty list passed in, quit

   15     | h::t ->

   16         h::(sieveOfEra

   17            (List.filter (fun x -> x % h <> 0) t))

   18 

   19 // Example:

   20 sieveOfEra [2..100]

   21  > val it : int list

   22 = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37;

   23     41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83;

   24     89; 97]

Actually, it too me a little bit to get the answer, in terms of programming. I had the recursion returning int -> list -> list instead of just int -> list. That is because in the match section, I was recursing the wrong data structure. Initially I had something like:

| h::t -> h::(List.filter

    (fun x -> x % h <> 0) t) sieveOfEra t

The best part is I figured out what I was doing wrong, just before I fell asleep this morning :-)