title: The sieve of Eratosthenes in F#
body: <p>I am interested in an implementation of the <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noreferrer">sieve of eratosthenes</a> in purely functional F#. I am interested in an implementation of the actual sieve, <a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf" rel="noreferrer">not the naive functional implementation that isn't really the sieve</a>, so not something like this:</p>
  
  <pre><code>let rec PseudoSieve list =
      match list with
      | hd::tl -&gt; hd :: (PseudoSieve &lt;| List.filter (fun x -&gt; x % hd &lt;&gt; 0) tl)
      | [] -&gt; []
  </code></pre>
  
  <p>The second link above briefly describes an algorithm that would require the use of a multimap, which isn't available in F# as far as I know. The Haskell implementation given uses a map that supports an <code>insertWith</code> method, which I haven't seen available in the <a href="http://msdn.microsoft.com/en-us/library/ee353686.aspx" rel="noreferrer">F# functional map</a>.</p>
  
  <p>Does anyone know a way to translate the given Haskell map code to F#, or perhaps knows of alternative implementation methods or sieving algorithms that are as efficient and better suited for a functional implementation or F#?</p>