Moim początkowym celem przy pisaniu było pozostawienie najmniejszego możliwego śladu. Mogę śmiało powiedzieć, że ten cel został osiągnięty. Niestety, to pozostawia mi dość powolną implementację. Aby wygenerować wszystkie liczby pierwsze poniżej 2 milionów, procesor Intel 3Ghz zajmuje około 8 sekund.

Czy mimo to można poprawić czas wykonywania tego kodu przy minimalnym poświęceniu niewielkiej ilości pamięci? Alternatywnie, czy nie mówię o tym w niewłaściwy sposób, patrząc na to z funkcjonalnego punktu widzenia?

KOD

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

Aktualizacja

Udoskonaliłem algorytm i udało mi się zgasić 2 sekundy, ale podwoiłem zużycie pamięci.

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

Aktualizacja

Najwyraźniej korzystałem ze starego kompilatora. W najnowszej wersji mój oryginalny algorytm zajmuje 6,5 s, a nie 8 s. To całkiem spora poprawa.