区间线性筛

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int N=1000005;
typedef long long LL;
int primes[N], n, cnt=0;
bool vis[N];
int l, r;

void Lseive(int n){ // 线性筛
    memset(primes, 0x00, sizeof primes);
    memset(vis, 0x00, sizeof vis);
    for(int i=2; i<=n; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=n/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    Lseive(50000);
    while(cin>>l>>r){
        memset(vis, 0x00, sizeof vis);
        for(int i=0; i<cnt; ++i){
            LL p=primes[i];
            for(LL j=max(2*p, (l+p-1)/p*p); j<=r; j+=p) vis[j-l]=true;
        }
        int knt=0;
        int sub[r-l+1];
        memset(sub, 0x00, sizeof sub);
        for(int i=0; i<=r-l; ++i){
            if(!vis[i] && i+l>1) sub[knt++]=i+l;
        }
        if(knt<2) cout<<"There are no adjacent primes."<<endl;
        else{
            int minp=0, maxp=0; // 存储下标
            for(int i=0; i+1<knt; ++i){
                int d=sub[i+1]-sub[i];
                if(d<sub[minp+1]-sub[minp]) minp=i;
                if(d>sub[maxp+1]-sub[maxp]) maxp=i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", sub[minp], sub[minp+1], sub[maxp], sub[maxp+1]);
        }
    }

    return 0;
}