Meu objetivo inicial ao escrever isso era deixar a menor pegada possível. Posso dizer com confiança que essa meta foi cumprida. Infelizmente, isso me deixa com uma implementação bastante lenta. Para gerar todos os primos abaixo de 2 milhões, demora cerca de 8 segundos em um chip Intel 3Ghz.

Existe alguma maneira de melhorar o tempo de execução deste código com o mínimo de sacrifício para a pequena pegada de memória? Alternativamente, eu estou indo sobre isso da maneira errada quando olhando para ele do ponto de vista funcional?

CÓDIGO

/// 6.5s for max = 2,000,000
let generatePrimeNumbers max =    
    let rec generate number numberSequence =
        if number * number > max then numberSequence else
        let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L)
        let newNumberSequence = seq { for i in filteredNumbers -> i }
        let newNumber = newNumberSequence |> Seq.find (fun x -> x > number)
        generate newNumber newNumberSequence                
    generate 2L (seq { for i in 2L..max -> i })

Atualizar

Eu ajustei o algoritmo e consegui reduzir em 2 segundos o consumo de memória.

/// 5.2s for max = 2,000,000
let generatePrimeNumbers max =    
    let rec generate number numberSequence =
        if number * number > max then numberSequence else
        let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) |> Seq.toArray |> Array.toSeq
        let newNumber = filteredNumbers |> Seq.find (fun v -> v > number)
        generate newNumber filteredNumbers                
    generate 2L (seq { for i in 2L..max -> i })

Atualizar

Aparentemente, eu estava usando um compilador antigo. Com a versão mais recente, meu algoritmo original usa 6,5s em vez de 8s. Isso é uma grande melhoria.