F# - Sieve Of Eratosthenes. Useful when solving some Euler Project challanges.

Post date: Aug 31, 2010 6:29:50 PM

let sieveOfErat max = let rec sieve l r = let r = List.Cons (List.hd l, r) let l = List.filter(fun x -> (x % r.Head <> 0I && x <> r.Head)) l match r.Head with | n when n > bigint.FromInt32(int (Math.Ceiling(Math.Sqrt (big_int.ToDouble max)))) -> List.append l r | n -> match (List.length l) with | 0 -> r | n -> sieve l r sieve [2I..max] [] let sieveOfEratSeq max = let rec sieve l r = let r = Seq.cons (Seq.hd l) r let l = Seq.filter(fun x -> (x % (Seq.hd r) <> 0I && x <> (Seq.hd r))) l match (Seq.hd r) with | n when n > bigint.FromInt32(int (Math.Ceiling(Math.Sqrt (big_int.ToDouble max)))) -> Seq.append l r | n -> match (Seq.length l) with | 0 -> r | n -> sieve l r sieve {2I..max} Seq.empty