AcWing 196. 质数距离

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

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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int p[N],cnt,vis[N],ans[N],num;
void pre()
{
    for(int i=2;i<N;i++)
    {
        if(!vis[i])p[++cnt]=i;
        for(int j=1;p[j]<N/i;j++)
        {
            vis[i*p[j]]=1;
            if(i%j==0)break;
        }
    }
}
int main()
{
    pre();
    int l,r;
    while(cin>>l>>r)
    {
        memset(vis,0,sizeof vis);
        num=0;
        for(int i=1;i<=cnt;i++)
        {
            ll pr=p[i];
            for(ll j=max(pr*2,(l+pr-1)/pr*pr);j<=r;j+=pr)
              vis[j-l]=1;
        }
        for(int i=0;i<=r-l;i++)
          if(!vis[i]&&i+l>=2)
            ans[++num]=i+l;
        if(num<2)puts("There are no adjacent primes.");
        else 
        {
            int minn=0x3f3f3f3f,nx,ny;
            int maxx=0,xx,xy;
            for(int i=1;i<num;i++)
            {
                int d=ans[i+1]-ans[i];
                if(d<minn)minn=d,nx=i,ny=i+1;
                if(d>maxx)maxx=d,xx=i,xy=i+1;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",ans[nx],ans[ny],ans[xx],ans[xy]);
        }
    }
    return 0;
}

 

上一篇:数据库安全小助手DBSAT


下一篇:AtCoder Beginner Contest 196 A~E题解