2
\$\begingroup\$

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 :)

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Jan 1 at 11:22
  • \$\begingroup\$ 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. :) \$\endgroup\$ Jan 3 at 2:00

1 Answer 1

2
\$\begingroup\$

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 ^^.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.