Mi objetivo inicial al escribir esto era dejar la huella más pequeña posible. Puedo decir con confianza que este objetivo se ha cumplido. Desafortunadamente, esto me deja con una implementación bastante lenta. Para generar todos los números primos inferiores a 2 millones, se necesitan aproximadamente 8 segundos en un chip Intel de 3 GHz.

¿Hay alguna forma de mejorar el tiempo de ejecución de este código con un mínimo sacrificio a la pequeña huella de memoria? Alternativamente, ¿estoy yendo por esto de manera incorrecta cuando lo veo desde un punto 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 })

Actualizar

Ajusté el algoritmo y logré eliminar 2 segundos pero el consumo de memoria doble.

/// 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 })

Actualizar

Aparentemente, estaba usando un viejo compilador. Con la última versión, mi algoritmo original toma 6.5s en lugar de 8s. Esa es toda una mejora.