Monday, May 13, 2013

Get prime numbers on F# (infinite)

(continued from phosphorescence: Get prime numbers on F# (finite))
Rewrite to get prime numbers on F# using Sieve of Eratosthenes algorithm with infinite sequence.
module Prime =
  let primeTable = ref (Seq.empty<int64>)
  let takeSmallerThanSquare n sequence =
    Seq.takeWhile (fun elem -> elem * elem <= n) sequence
  let existsMultiple n sequence =
    Seq.exists (fun elem -> n % elem = 0L) sequence
  let isPrimeElement elem =
    match (existsMultiple elem <| takeSmallerThanSquare elem !primeTable) with
    | true -> None
    | false -> primeTable := Seq.append !primeTable (Seq.singleton elem);Some(elem)
  let seedSeq = Seq.append
                <| Seq.ofList [2L; 3L; 5L; 7L]
                <| Seq.unfold
                     (fun (current, next) ->
                       match next % 10L with
                       | 3L -> Some(current, (next, next + 4L))
                       | _ -> Some(current, (next, next + 2L))
                     ) (11L, 13L)
  let sieveOfEratosthenes = Seq.choose isPrimeElement seedSeq


And I put this in github.

It takes little faster than finite one.
> Seq.last <| Seq.take 1000 Prime.sieveOfEratosthenes;;
val it : int64 = 7919L

No comments:

Post a Comment