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 :-)

## 2 comments:

The solution isn't really the same; you should read "The Genuine Sieve of Eratosthenes" by Melissa O'Neill.

Thanks for taking a look at my soluton. I just followed the algorithm on Wikipedia. As soon as I have the time, I will take a look at your recommendation.

Post a Comment