【题解】poj2689（LibreOJ10197） 线性筛

题目链接
筛出2到sqrt(u)的所有质数，再标记[l,u]中是质数p倍数的数，最后枚举相邻质数
部分代码实现参考了大佬题解

题目描述

给定两个整数 L , R L,R L,R，求闭区间 [ L , R ] [L,R] [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。

输入格式

多组数据。每行两个数 L , R L,R L,R。

输出格式

详见输出样例。

样例

样例输入

2 17
14 17

样例输出

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

数据范围与提示

对于全部数据， 1 ≤ L &lt; R &lt; 2 31 , R − L ≤ 1 0 6 1\le L\lt R\lt 2^{31},R-L\le 10^6 1≤L<R<231,R−L≤106。

#include<cstdio>
#include<cstring>
#include<climits>
#include<cmath>
const int N=5e4+10;
const int M=1e6+10;
int l,u;
bool iscomp[N+10];
int vis[M];
int prime[N+10],p;
void primetable()//之前筛小了…… 
{
	for(int i=2;i<=(int)sqrt(N+0.5);i++)
	    if(!iscomp[i])
	    {
		    for(int j=i*i;j<N;j+=i)
		        iscomp[j]=1;
	    }
	for(int i=2;i<N;i++)if(!iscomp[i])prime[p++]=i;
}
int maxn,minn;
int c1,c2,d1,d2;
int main()
{
	//freopen("in.txt","r",stdin);
	primetable();
	while(~scanf("%d%d",&l,&u))
	{
		maxn=-1,minn=1e9;
		int tmp=-1;
		if(l==1)l=2;
		memset(vis,0,sizeof(vis));//好久没写多组数据又忘了… 
		for(int i=0;i<p;i++)
		{
			int a=(l-1)/prime[i]+1,b=u/prime[i];
			for(int j=a;j<=b;j++)
		        if(j>1)vis[j*prime[i]-l]=1;//注意这个-l，记录偏移量
		}
	    for(int i=0;i<=u-l;i++)
	    {
	    	if(!vis[i])
			{
				if(tmp==-1)//之前把tmp初值赋的0，i=0时并没有刷新，于是出问题了 
	    	    {
	    		    tmp=i;continue;
			    }
			    if(maxn<i-tmp)maxn=i-tmp,d1=tmp+l,d2=i+l;
			    if(minn>i-tmp)minn=i-tmp,c1=tmp+l,c2=i+l;//还原
			    tmp=i;
			} 
		}
		if(maxn==-1)puts("There are no adjacent primes.");
		else printf("%d,%d are closest, %d,%d are most distant.\n",c1,c2,d1,d2);
	}
	return 0;
}

总结

这种解法好像挺爱考的