Bitwise optimised seive

general
, ,
1

I tried a lot but I am unable to understand bitwise seive…I know the basic seive.Pleae help me understand the bitwise seive and how it works?
The code with which I am busy with is—

#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=ii, k=i<<1; j<LIMLIM; j+=k)
isc(j);
}

2


read the last para

3

Thaks for the link.
I have understood how ifc is working.But I have some doubt in isc(n).
Suppose we want to set 5th bit of index to 1. Then we will do 1<<5 and thus change 1 to 10000 and assign it to flag[n>>6].
But if 3rd bit of this index was 1 previously ,won’t it change to 0 now?and then it should not give desired output.Please tell me where I am wrong.Thanks in advance.

4

I got it!!and thanks!