digitalBush

Here is the third(hopefully of many) implementations of the Sieve of Eratosthenes. F# has been making a lot of noise lately, so let's see what's up.

let findPrimes max=
    seq {
        yield 2
        let maxSquareRoot:int = int (sqrt (float max))
        let primes = Array.create (max+1) true
        for n in 3 .. 2 .. max do
            if primes.[n] then
                if n<=maxSquareRoot  then
                    for i in n*n..2*n..max do primes.[i] <- false
                yield n
    }

I struggled a bit with F#. Functional languages have a different look and feel for sure. The hardest part of this was that I had several ways to implement this. I'm still not sure I chose the most optimal way since this is the slowest one so far. My first stab used lists like so:

let getPrimes max =
    let maxSquareRoot:int = int (sqrt (float max))
    let primes = Array.create (max+1) true    

    2::[3 .. 2 .. max]
    |>List.filter(fun n->
        if primes.[n] && n<=maxSquareRoot  then
            for i in n*n..2*n..max do primes.[i] <- false
        primes.[n]
    )

This version was slower than what I ultimately wrote up top using sequences, but I really like the pipe syntax. I think both versions are very compact and easy to follow. I'm a little bummed that both versions are slower than my C# version. If anyone can help me write a better(faster) version, I'd love the help. I feel like I'm not seeing the full potential of the language and I'm missing something huge.