SP503 题解

· · 题解

题目大意

多组询问给出 l,r，求出 [l,r] 之间所有的素数。1\le l,r\le 2^{31}，1\le r-l\le 1000000。

思路

注意到 1\le l,r\le 2^{31}，范围过大，不能线性筛直筛出来所有素数。但是我们注意到区间长度并不大，考虑利用埃氏筛的原理。

具体来讲，一个合数 x 必定有一个小于等于 \sqrt{x} 的质因数，这个显然。我们先筛出来 \sqrt{2^{31}} 之内的素数（大概 50000)，然后对于给出的区间标记出我们所有的质数的倍数，剩下的一定是素数。

我们在处理区间时把数组下标减去左端点，这样标记合数的数组只需要开到 1000010 就够了。多组测试数据，记得清空。代码如下：

signed main(){
    isp[0]=isp[1]=1;
    for(int i=2;i<=MAXX;i++){
        if(!isp[i]) p[++hop]=i;
        for(int j=1;j<=hop&&i*p[j]<=MAXX;j++){
            isp[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
    t=read();while(t--){
        memset(isP,0,sizeof(isP));l=read(),r=read();
        for(int i=1;i<=hop;i++)
            for(int j=l/p[i];j<=r/p[i];j++){
                if(j==1) j++;
                isP[j*p[i]-l]=1;
            }
        for(int i=0;i<=r-l;i++) if(!isP[i]) printf("%lld\n",i+l);
    }
    return 0;
}