title: Fastest way to calculate primes in C#?
body: <p>I actually have an answer to my question but it is not parallelized so I am interested in ways to improve the algorithm. Anyway it might be useful as-is for some people.</p>
  
  <pre><code>int Until = 20000000;
  BitArray PrimeBits = new BitArray(Until, true);
  
  /*
   * Sieve of Eratosthenes
   * PrimeBits is a simple BitArray where all bit is an integer
   * and we mark composite numbers as false
   */
  
  PrimeBits.Set(0, false); // You don't actually need this, just
  PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime
  
  for (int P = 2; P &lt; (int)Math.Sqrt(Until) + 1; P++)
      if (PrimeBits.Get(P))
          // These are going to be the multiples of P if it is a prime
          for (int PMultiply = P * 2; PMultiply &lt; Until; PMultiply += P)
              PrimeBits.Set(PMultiply, false);
  
  // We use this to store the actual prime numbers
  List&lt;int&gt; Primes = new List&lt;int&gt;();
  
  for (int i = 2; i &lt; Until; i++)
      if (PrimeBits.Get(i))
          Primes.Add(i);
  </code></pre>
  
  <p>Maybe I could use multiple <code>BitArray</code>s and <a href="http://msdn.microsoft.com/en-us/library/system.collections.bitarray.and.aspx" rel="noreferrer">BitArray.And()</a> them together?</p>