Sieve of Eratosthenes in F#

Question

after looking at the pseudocode for the Sieve of Eratosthenes on wikipedia I tried implementing a similar version using F#. The code runs just fine, that is, it returns all prime numbers up until a given number. But I was wondering if the implementation could be improved. See below for the code:

let rec sieve xs count maxNumb = match count = maxNumb with | true -> xs | false when (Array.contains count xs) -> xs |> Array.filter (fun ys -> ys % count <> 0. || ys = count) |> fun filteredArr -> sieve filteredArr (count + 1.) maxNumb | false -> sieve xs (count + 1.) maxNumb let findPrimes maxNumb = sieve [|2. .. maxNumb|] 2. maxNumb

findPrimes 30. [|2.0; 3.0; 5.0; 7.0; 11.0; 13.0; 17.0; 19.0; 23.0; 29.0|]

Thank you in advance for any comments or remarks :)

You might be interested in Melissa O'Neill's paper The Genuine Sieve of Eratosthenes which explains how the classic Haskell one-liner is, in fact, not actually the Sieve of Eratosthenes, what – in her opinion – are the important traits of what makes program a "genuine" implementation of the Sieve of Eratosthenes, then shows a lazy, purely functional implementation of an algorithm that does exhibit the traits she defined as "genuine". While the laziness part is not directly applicable to F#, the rest is. — Jörg W Mittag
– Jörg W Mittag, Commented Jan 1, 2022 at 11:22
Thank you so much Jörg W Mittag! I just had a look at the paper, I will definitely come back with a better implementation. :) — Antônio Salomão
– Antônio Salomão, Commented Jan 3, 2022 at 2:00

JanDotNet · Accepted Answer · 2022-01-09 17:27:05Z

One small improvement. You can remove one of the recursive calles which improves readability and enables the compiler to use tail recursion:

let rec sieve xs count maxNumb = if count = maxNumb then xs else let xs' = if xs |> Array.contains count then xs |> Array.filter (fun ys -> ys % count <> 0. || ys = count) else xs sieve xs' (count + 1.) maxNumb

Further more, I was wondering why not using a list instead of the array because lists are more "functional-like". Comparing the performance of list usage vs. array usage, the array was 10 times faster ^^.

Stack Exchange Network

Sieve of Eratosthenes in F#

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Sieve of Eratosthenes in F#

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions