acwing 196题解

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=1e6+3e5,M=1e5;
ll st[N],prime[N],cnt=0,pos,primes[N];
void init()
{
    for(int i=2;i<M;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;i*prime[j]<M;j++)
        {
            st[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    pos=cnt;
}//存了2^31-1里面的最小质因子.

signed main()
{
    init();
    int l,r;
    while(cin>>l>>r)
    {
        cnt=pos;
        memset(st,0,sizeof st);
        for(int i=0;i<cnt;i++)
        {
            for(ll j=max(2*prime[i],(l+prime[i]-1)/prime[i]*prime[i]);j<=r;j+=prime[i])
            {
                st[j-l]=true;
            }
        }
        cnt=0;
        for(int i=0;i<=r-l;i++)
        {
            if(!st[i]&&i+l>=2) primes[cnt++]=i+l;
        }
        if(cnt<2) puts("There are no adjacent primes.");
        else
        {
            int mi=2e9,mx=-1;
            int ta,tb,tc,td;
            for(int i=1;i<cnt;i++)
            {
                if(primes[i]-primes[i-1]>mx)
                {
                    mx=primes[i]-primes[i-1];
                    ta=primes[i-1];
                    tb=primes[i];
                }
                if(primes[i]-primes[i-1]<mi)
                {
                    mi=primes[i]-primes[i-1];
                    tc=primes[i-1];
                    td=primes[i];
                }
            }
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",tc,td,ta,tb);
        }
    }
    return 0;
}