title: Sieve of eratosthenes : bit wise optimized
body: <p>After searching the net I came to know that the bit-wise version of the sieve of eratosthenes is pretty efficient.
  The problem is I am unable to understand the math/method it is using.</p>
  
  <p>The version that I have been busy with looks like this: </p>
  
  <pre><code>#define MAX 100000000
  #define LIM 10000
  
  unsigned flag[MAX&gt;&gt;6]={0};
  
  #define ifc(n) (flag[n&gt;&gt;6]&amp;(1&lt;&lt;((n&gt;&gt;1)&amp;31)))         //LINE 1
  #define isc(n) (flag[n&gt;&gt;6]|=(1&lt;&lt;((n&gt;&gt;1)&amp;31)))        //LINE 2
  
  void sieve() {
      unsigned i, j, k;
      for(i=3; i&lt;LIM; i+=2)
          if(!ifc(i))
              for(j=i*i, k=i&lt;&lt;1; j&lt;LIM*LIM; j+=k)
                  isc(j);
  }
  </code></pre>
  
  <p>Points that I understood (Please correct me if I am wrong):    </p>
  
  <ol>
  <li>Statement in line 1 checks if the number is composite.</li>
  <li>Statement    in line 2 marks the number 'n' as composite.</li>
  <li>The program is storing    the value 0 or 1 at a bit of an int. This tends to reduce the memory    usage to x/32. (x is the size that would have been used had an int    been used to store the 0 or 1 instead of a bit like in my solution    above)</li>
  </ol>
  
  <p>Points that are going above my head as of now :</p>
  
  <ol>
  <li>How is the finction in LINE 1 functioning.How is the function making sure that the number is composite or not.</li>
  <li>How is function in LINE 2 setting the bit.</li>
  <li>I also came to know that the bitwise sieve is timewise efficient as
  well. Is it because of the use of bitwise operators only or
  something else is contributing to it as well.</li>
  </ol>
  
  <p>Any ideas or suggestions?</p>