title: Can the execution time of this prime number generator be improved?
body: <p>My initial goal when writing this was to leave the smallest footprint possible. I can say with confidence that this goal has been met. Unfortunately, this leaves me with a rather slow implementation. To generate all primes below 2 million it takes about 8 seconds on a 3Ghz Intel chip.</p>
  
  <p>Is there anyway to improve the execution time of this code with minimal sacrifice to the small memory footprint? Alternatively, am I going about this the wrong way when looking at it from a functional standpoint?</p>
  
  <p><strong>CODE</strong> </p>
  
  <pre><code>/// 6.5s for max = 2,000,000
  let generatePrimeNumbers max =    
      let rec generate number numberSequence =
          if number * number &gt; max then numberSequence else
          let filteredNumbers = numberSequence |&gt; Seq.filter (fun v -&gt; v = number || v % number &lt;&gt; 0L)
          let newNumberSequence = seq { for i in filteredNumbers -&gt; i }
          let newNumber = newNumberSequence |&gt; Seq.find (fun x -&gt; x &gt; number)
          generate newNumber newNumberSequence                
      generate 2L (seq { for i in 2L..max -&gt; i })
  </code></pre>
  
  <p><strong>Update</strong></p>
  
  <p>I tweaked the algorithm and managed to shave off 2 seconds but double memory consumption.</p>
  
  <pre><code>/// 5.2s for max = 2,000,000
  let generatePrimeNumbers max =    
      let rec generate number numberSequence =
          if number * number &gt; max then numberSequence else
          let filteredNumbers = numberSequence |&gt; Seq.filter (fun v -&gt; v = number || v % number &lt;&gt; 0L) |&gt; Seq.toArray |&gt; Array.toSeq
          let newNumber = filteredNumbers |&gt; Seq.find (fun v -&gt; v &gt; number)
          generate newNumber filteredNumbers                
      generate 2L (seq { for i in 2L..max -&gt; i })
  </code></pre>
  
  <p><strong>Update</strong></p>
  
  <p>Apparently, I was using an old compiler. With the latest version my original algorithm takes 6.5s rather than 8s. That is quite an improvement.</p>