质数距离

给定两个整数L和U，你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2（即C2-C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1和D2（即D1-D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数L和U，其中L和U的差值不会超过1000000。

输出格式

对于每个L和U ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。

数据范围

$1≤L<U≤2^{31}−1$
输入样例：

2 17
14 17

输出样例：

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

思路

对于[L,R]范围内的任意一个合数，其最小质因数都会小于$\sqrt(2^{31}-1)$，所以可以先将[2,1<<16]范围内的质数筛选出来，然后给定一个[L,R]，就用筛选出来的质数去筛[L,R]的合数，筛完合数，剩下的就是质数，另外这里需要统计将下标-L,不然会爆内存，记录结果的时候再加上L即可。

#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
const ll maxn = (1<<16)+10;
typedef pair<ll,ll> pii;

ll L,R;
bool vis[maxn];
ll P[maxn],tail;
bool vis2[1000010];
void init(){
    for(ll i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j =i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}
void fun(){
    ll a = -1,b = -1,c = -1,d = -1,mi = 2e9,mx = -1;
    memset(vis2,0,sizeof vis2);
    for(ll i = 0;i<tail && P[i]*P[i]<=R;i++){
        for(ll j = (L+P[i]-1)/P[i];j<=R/P[i];j++){
            if(j == 0 || j == 1) continue;
            vis2[P[i]*j-L] = true;
        }
    }
    ll last = -1;bool find = false;
    for(ll i = 0;i<=R-L;i++){
        if(vis2[i]) continue;
        if(last != -1 && i-last<mi){
            mi = i-last;
            a = last+L,b = i+L;
            find = true;
        }
        if(last != -1 && i-last>mx){
            mx = i-last;
            c = last+L,d = i+L;
        }
        last = i;
    }
    if(!find){
        puts("There are no adjacent primes.");
    }else{
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",a,b,c,d);
    }

}
int main(){
    init();
    while(scanf("%lld %lld",&L,&R) != EOF){
        if(L == 1) L = 2;
        fun();
    }

    return 0;
}