题意：给定两个整数 L,RL,R，1≤L≤R≤231,R−L≤1061\leq L \leq R\leq 2^{31},R-L\leq 10^6，求闭区间 [L,R][L,R] 中相邻两个质数的差最大和最小是多少，输出这两个质数。

由题意可知，L,RL,R 的范围过大，肯定不能直接生成 [1,R][1,R] 之间的所有质数。

但是 R−LR-L 的范围很小，我们可以直接筛出 2∼R2\sim R 之间的所有质数，并把 L∼RL\sim R 之间能被这些质数整除的数标记，最后只要看所有没被标记的数，相邻质数两两比较，找出差值最大即可。

时间复杂度：

O(∑p∈质数,p≤RR−Lp)=O(Rlog⁡log⁡R+(R−L)log⁡log⁡R) O(\sum_{p\in\text{质数},p\le\sqrt{R}}\frac{R-L}{p})=O(\sqrt{R}\log\log\sqrt{R}+(R-L)\log\log R)

code:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long l,r,cnt,maxx,minn,maxi,mini;
long long prime[1501010],vis[1501010];
int main()
{
	while(scanf("%lld%lld",&l,&r)!=EOF)
	{
		if((l<=1&&r<=1)||l>=r)
		{
			printf("There are no adjacent primes.\n");
			continue;
		}
		memset(prime,0,sizeof(prime));
		memset(vis,0,sizeof(vis));
		cnt=0;
		maxx=0;
		mini=0;
		minn=2147483648;
		maxi=0;
		long long n=sqrt(r)+1;
		for(int i=2;i<=n;i++)
		{
			if(vis[i]==0)
			{
				vis[i]=i;
				prime[++cnt]=i;
			}
			for(int j=1;j<=cnt;j++)
			{
				if(prime[j]>vis[i]||prime[j]*i>n)
					break;
				vis[i*prime[j]]=prime[j];
			}
		}
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=cnt;i++)
		{
			int p=prime[i];
			int d=l/p;
			int u=r/p;
			for(int j=d;j<=u;j++)
				if(j>1)
					vis[p*j-l]=1;
		}
		memset(prime,0,sizeof(prime));
		cnt=0;
		for(int i=max(l,(long long)2);i<=r;i++)
			if(!vis[i-l])
				prime[++cnt]=i;
		if(cnt==1)
		{
			printf("There are no adjacent primes.\n");
			continue;
		}
		for(int i=2;i<=cnt;i++)
		{
			if(prime[i]-prime[i-1]>maxx)
			{
				maxx=prime[i]-prime[i-1];
				maxi=i-1;
			}
			if(prime[i]-prime[i-1]<minn)
			{
				minn=prime[i]-prime[i-1];
				mini=i-1;
			}
		}
		printf("%lld,%lld are closest, %lld,%lld are most distant.\n",prime[mini],prime[mini+1],prime[maxi],prime[maxi+1]);
	}

    return 0;
}