title: Problems with large bool array in C#
body: <p>I decided to write a prime number generator as an easy excerise. The code is pretty simple:</p>
  
  <pre><code>static void generatePrimes (long min, long max)
      {
  
          bool[] prime = new bool[max + 1];
  
          for (long i=2; i&lt;max+1; i++)
              prime [i] = true;
  
          for (long i=2; i&lt;max+1; i++) {
              if (prime [i]) {
                  if (i&gt;=min)
                      Console.WriteLine (i);
                  for (long j=i*2; j&lt;max+1; j+=i)
                      prime [j] = false;
              }
          }
  
          Console.WriteLine ();
  
      }
  </code></pre>
  
  <p>It works just fine with input like 1..10000. However, around max=1000000000 it starts to work EXTREMELY slow; also, mono takes about 1Gb of memory. To me, it seems kinda strange: shouldn't  the bool[1000000000] take 1000000000 bits, not bytes? Maybe I'm making some stupid mistake that I don't see that makes it so uneffective?</p>