Ox31质数

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

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

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

输出格式
对于每个和 ，输出一个结果，结果占一行。

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

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

数据范围

输入样例：

2 17
14 17

输出样例：

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

代码：

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long ll;
const ll MAX_N=1e6+5;
ll v[MAX_N],prime[MAX_N];
ll vis[MAX_N],primes[MAX_N];
ll m;
void Prime(ll n){
    memset(v,0,sizeof(v));//最小质因子
    m=0;//质数数量
    for(ll i=2;i<=n;i++){
        if(v[i]==0){//i是质数
            v[i]=i;
            prime[++m]=i;
        }
        for(ll j=1;j<=m;j++){
            //i有比prime[j]更小的质因子,或者超出n的范围
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
}
int main(){
    ll L,U;
    while(cin>>L>>U){
        ll n = sqrt(U)+1;
        Prime(n);
        memset(vis,0,sizeof(vis));
        memset(primes,0,sizeof(primes));
        for(ll i=1;i<=m;i++){
            ll p = prime[i];
//            if(L<p) break;
            // 把[L,U]之间P的倍数删掉
            ll x = ceil(L/p)*p;
            ll y = max(x,2*p);
            for(ll j=y;j<=U;j+=p){
                vis[j-L]=true;
            }
        }
        ll cnt=0;
        for(ll i=0;i<=U-L;i++){
            if(!vis[i]&&i+L>1){
                primes[++cnt]=L+i;
            }
        }
        if(cnt<2){
            cout<<"There are no adjacent primes."<<endl;
            continue;
        }
        ll minn=1,maxx=1;
        for(ll i=1;i+1<=cnt;i++){
            ll d = primes[i+1]-primes[i];
            if(primes[minn+1]-primes[minn]>d) minn=i;
            if(primes[maxx+1]-primes[maxx]<d) maxx=i;
        }
        cout<<primes[minn]<<","<<primes[minn+1]<<" are closest, "<<primes[maxx]<<","<<primes[maxx+1]<<" are most distant."<<endl;
    }
    return 0;
}