Project Euler‎ > ‎

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

posted Aug 31, 2010, 11:29 AM by Peter Henell
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

Comments