Friday, May 10, 2013

Get prime numbers on F# (finite)

Get prime numbers on F# using Sieve of Eratosthenes algorithm.
module Prime =
  let sieveOfEratosthenes = seq {
    let primeTable = ref (Seq.ofList [2L ;3L ;5L ;7L])
    let sieve'sSeed = [11L; 13L; 17L; 19L]
    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 sieve digit =
      let isPrimeElement seed =
        let elem = digit * 10L + seed
        match (existsMultiple elem <| takeSmallerThanSquare elem !primeTable) with
        | true -> None
        | false -> Some(elem)
      primeTable := Seq.append !primeTable (Seq.choose isPrimeElement sieve'sSeed)
    List.iter (fun i -> sieve i) [0L..500L]
    yield! !primeTable

It's finite, and it takes long time (so I stop the number around 5000).
> Seq.last Prime.sieveOfEratosthenes;;
val it : int64 = 5011L
(continue to phosphorescence: Get prime numbers on F# (infinite))

No comments:

Post a Comment