算法与acm

筛选法求素数

2010年4月1日 阅读(209)

const long maxn=1000001;
bool prime[maxn];
//筛选法求素数
//0代表素数,1代表非素数

void primeinit(){
long long i=2,t;
for(i=4;i<maxn;i=i+2)
prime[i]=false;
for(i=3;i<maxn;i=i+2)
{

    if(prime[i])
    {
        t=i*i;
        while(t<maxn)
        {
        prime[t]=false;
        t=t+i;//<<2;//偶数倍不用检测i*i为奇数,故i*i+2i必为奇数
        }

    }

}

}

 

You Might Also Like