「UVA10140」 Prime Distance 解题报告

题面

大概的意思就是求 $[l,r]$ 区间相邻最近和最远的质数

解题思路

这里明显的就是一个埃氏筛的运用（很久前咕掉的现在补上

分析

区间的长度不超过 $1e6$，又有筛质数时，有效的其实是小于 $n$ 的质数，因此可以先预处理出 $[1,\sqrt{\mathtt{INT\_MAX}}]$ 的质数，然后在用其取筛 $[l,r]$ 区间的质数，直接那个 $O(n\log\log n)$ 的Eratosthenes 筛法即可

Warning

1、$1$ 也算质数

2、筛素数的时候可能会把这个质数本身筛掉

Code

#include<bits/stdc++.h>
#define rgt register
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f7f
#define M 1000007
using namespace std;
const int N=sqrt(INT_MAX);
LL l,r,t,Max,Min,lx,ly,rx,ry,x,y,pr[N>>1];
bool v[N+3],b[M];
int main() {
    rll i,j,c;
    for(i=2;i<=N;i++) {//初始化质数
        if(!v[i]) pr[++t]=i;
        for(j=1;j<=t;j++) {
            c=i*pr[j];if(c>N) break;
            v[c]=1;if(i%pr[j]==0) break;
        }
    }
    while(~scanf("%lld%lld",&l,&r)) {
        memset(b,0,sizeof(b)),Max=-1,Min=inf+1,y=-1;
        if(l==1) b[0]=1;
        for(i=1;i<=t&&pr[i]<=r;i++) {
            c=pr[i]*max(l/pr[i]+(l%pr[i]>0),2ll);//取max是防止不筛掉自己
            while(c<=r) b[c-l]=1,c+=pr[i];//标记合数
        }
        for(i=0;i<=r-l;i++)
            if(!b[i]) {
                x=y,y=i+l;
                if(x<0) continue;
                if(y-x<Min)    lx=x,ly=y,Min=y-x;
                if(y-x>Max) rx=x,ry=y,Max=y-x;
            }
        if(Max<0||Min>inf) printf("There are no adjacent primes.\n");
        else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",lx,ly,rx,ry);
    }
    return 0;
}