primes.fs

let countPrimes n =
    let rec outer count i =
        if i <= n then
            let sqrtI = int (floor (sqrt (float i)))
            let rec inner j =
                if j <= sqrtI then
                    if i % j <> 0 then
                        inner (j+1)
                    else
                        false
                else
                    true
            if inner 2 then
                outer (count+1) (i+1)
            else
                outer count (i+1)
        else
            count

    outer 0 2

let countPrimesBySeq n =
    Seq.initInfinite (fun i -> i + 2)
    |> Seq.takeWhile (fun i -> i <= n)
    |> Seq.filter (fun i ->
        let sqrtI = int (floor (sqrt (float i)))
 
        Seq.initInfinite (fun j -> j + 2)
        |> Seq.takeWhile (fun j -> j <= sqrtI)
        |> Seq.forall (fun j -> i % j <> 0))
    |> Seq.length

let countPrimesByISeq n =
    ISeq.initInfinite (fun i -> i + 2)
    |> ISeq.takeWhile (fun i -> i <= n)
    |> ISeq.filter (fun i ->
        let sqrtI = int (floor (sqrt (float i)))
 
        ISeq.initInfinite (fun j -> j + 2)
        |> ISeq.takeWhile (fun j -> j <= sqrtI)
        |> ISeq.forall (fun j -> i % j <> 0))
    |> ISeq.length

open Nessos.Streams

let countPrimesByStreams n =
    Stream.initInfinite (fun i -> i + 2)
    |> Stream.takeWhile (fun i -> i <= n)
    |> Stream.filter (fun i ->
        let sqrtI = int (floor (sqrt (float i)))
 
        Stream.initInfinite (fun j -> j + 2)
        |> Stream.takeWhile (fun j -> j <= sqrtI)
        |> Stream.forall (fun j -> i % j <> 0))
    |> Stream.length
 
open System.Linq
 
let countPrimesByLinq n =
   Enumerable
    .Range(2, System.Int32.MaxValue-2)
    .TakeWhile(fun i -> i <= n)
    .Where(fun i ->
       let sqrtI = int (floor (sqrt (float i)))
 
       Enumerable
        .Range(2, System.Int32.MaxValue-2)
        .TakeWhile(fun j -> j <= sqrtI)
        .All(fun j -> i % j <> 0))
    .Count ()
 
let time what f =
    let sw = System.Diagnostics.Stopwatch.StartNew ()
    let count = f 500000
    printfn "%s: %d (%d)" what sw.ElapsedMilliseconds count
 
[<EntryPoint>]
let main argv =
    for i = 1 to 5 do
        time "old skool" countPrimes
        time "Seq"    countPrimesBySeq
        time "ISeq"   countPrimesByISeq
        time "Nessos" countPrimesByStreams
        time "Linq"   countPrimesByLinq

        printfn "\n"
    0

64-bit

old skool: 67 (41538)
Seq: 3651 (41538)
ISeq: 190 (41538)
Nessos: 471 (41538)
Linq: 428 (41538)

32-bit

old skool: 67 (41538)
Seq: 5007 (41538)
ISeq: 237 (41538)
Nessos: 903 (41538)
Linq: 435 (41538)