素数筛法

 新型素数筛法，和之前的不一样的地方在于以前的tag[i]表示i是否为素数,tag[i]=0表示i为素数。现在tag[i]表示[i*64,(i+1)*64-1]这64个数中的32个奇数是不是素数，tag用无符号整数，正好可以保存32位……

const int MAX=100000000;
u32 tag[MAX/64+1];
int prime[6000000],cnt;

void init()
{
    prime[cnt++]=2;
    int i,j;
    for(i=3;i<=MAX;i+=2) if(!(tag[i>>6]&(1<<(i/2%32))))
    {
        prime[cnt++]=i;
        for(j=i*3;j<=MAX;j+=i*2) tag[j>>6]|=(1<<(j/2%32));
    }
}