博客

质数距离（Liuser’s OJ）

题目

题目描述

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

输入格式

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

输出格式

对于每个L和R ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（详见样例1输出）

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

样例

样例1输入

2 17
14 17

样例1输出

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

数据范围

1<=L<R<=2147483647，R-L<=1000000

分析

由于L和R的范围很大，所以，直接通过素数筛跑出答案会超时，但是，L和R的区间较小，因此我们可以先通过素数筛跑出2~sqrt（R）的所有素数，对于每个素数a，把【L，R】中所有能被a整除的数（i*a）（合数）标记，所有未被标记的数就是素数，把相邻的2个素数比较，找出差最小和最大的。–lhy

AC代码+注释

#include<bits/stdc++.h>
using namespace std;

long long l,r,s[1000005],prime[1000005],f[1000005],cnt=0,a,b,p,Max,Min,x,y,x2,y2;

int main()
{
	memset(prime,1,sizeof(prime));
	prime[0]=prime[1]=0;
	for(long long i=2;i<=100005;i++)
	{
		if(prime[i])
		{
			s[cnt++]=i;
			//cnt是素数个数 
		}
		for(long long j=1;j<cnt&&s[j]*i<100005;j++)
		{
			prime[s[j]*i]=0;
		}
	}
	//素数筛，找出素数 
	while(scanf("%lld%lld",&l,&r)!=EOF)
	{
		if(l==1)
		{
			l=2;
		}
		//l==1时注意l要变成2 
		memset(f,0,sizeof(f));
		for(long long i=0;i<cnt;i++)
		{
			a=(l-1)/s[i]+1;
			b=r/s[i];
			for(long long j=a;j<=b;j++)
			{
				if(j>1)
				{
					f[j*s[i]-l]=1;
					//标记合数，1表示合数 
				}
			}
		}
		p=-1;
		Max=-1;
		Min=0x3f3f3f3f;
		for(long long i=0;i<=r-l;i++)
		{
			if(!f[i])
			{
				if(p==-1)
				{
					p=i;
					continue;
				}
				if(Max<i-p)
				{
					Max=i-p;
					x=p+l;
					y=i+l;
				}
				//差值最大的数对 
				if(Min>i-p)
				{
					Min=i-p;
					x2=p+l;
					y2=i+l;
				}
				//差值最小的数对 
				p=i;
			}
		}
		if(Max==-1)
		{
			printf("There are no adjacent primes.\n");
		}
		else
		{
			printf("%lld,%lld are closest, %lld,%lld are most distant.\n",x2,y2,x,y);
		}
	}
	return 0;
}