After searching the net i came to know that the bitwise version is pretty efficient.
The problem is i am unable to understand the math/method it is using.
The version that i have been busy with looks likes :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#define MAX 100000000
#define LIM 10000
unsigned flag[MAX>>6]={0};
#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31))) //LINE 1
#define isc(n) (flag[n>>6]=(1<<((n>>1)&31))) //LINE 2
void sieve() {
unsigned i, j, k;
for(i=3; i<LIM; i+=2)
if(!ifc(i))
for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
isc(j);
}
 
Points that I understood (Please correct me if I am wrong):
1)Statement in line 1 checks if the number is composite.
2)Statement in line 2 marks the number 'n' as composite.
3)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)
Points that are going above my head as of now :
1)How is the finction in LINE 1 functioning.How is the function making sure that the number is composite or not.
2)How is function in LINE 2 setting the bit.
3)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.
Please give any additional info if you have.
Any sort of help is highly appreciated.
Thanks a lot.