AcWing 196. 质数距离

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int prime[N],p[N];
bool vis[N];
int main() {
    int cnt = 0;
    for (int i = 2; i <= 50000; i++) {
        if (!vis[i]) prime[cnt++] = i;
        for (int j = 0; prime[j] * i <= 50000; j++) {
            vis[prime[j] * i] = true;
            if (i%prime[j] == 0) break;
        }
    }
    ll l,r;
    while(~scanf("%lld%lld",&l,&r)){
        memset(vis,0,sizeof(vis));
        for (int i = 0; i < cnt; i++) {
            int x = prime[i];
            for (ll j = max((l+x-1)/x*1ll*x,2ll*x); j <= r;  j+=x)
                vis[j-l] = true;
        }
        int num = 0;
        for(int i = 0; i <= r-l; i++) 
            if (!vis[i] && i+l>1) p[num++] = l+i;
        int maxd = 0,maxid,mind = N,minid;
        for (int i = 1; i < num; i++) {
            int d = p[i] - p[i-1];
            if (d > maxd) maxd = d,maxid = i;
            if (d < mind) mind = d,minid = i;
        }
        if (maxd == 0&&mind == N) 
            printf("There are no adjacent primes.\n");
        else printf("%d,%d are closest, %d,%d are most distant.\n",p[minid-1],p[minid],p[maxid-1],p[maxid]);
    }
    return 0;
}