筛选法求素数
2010年4月1日 阅读(348)
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必为奇数
}