最遥远的距离

世界上最遥远的距离，并不是天与地

而是我站在你身后，看着你偷偷的划水。。。

现在有一个质数村，村子里住着许多质数，但它们的权值均在区间[L,R]之间

现在小J想知道这个区间内距离最接近的两个相邻的质数

如果存在相同距离的其他相邻质数对，则输出第一对。

例如5与7的距离为2，11与13的距离也为2，但前者更优先

同理，他还希望找出距离最远的。

如果找不到输出"Not find"

Format
Input
多组数据，请做到文件底结束

每行输入两个整数L和U，其中L和U的差值不会超过1000000

1≤L<U≤2^31−1

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

详见样例

Samples
输入数据 1
2 17
14 17
输出数据 1
2 3 7 11
Not find

Sol:类比下埃式筛法

发现我们要筛去的是[L,R]这一段的合数

而对于[1,R]这一段的所有合数，其较小的质因子均不超过sqrt(R)

于是找出所有小于等于sqrt(R)的质数，然后使用埃式筛法，去筛[L,R]这一段的合数。

在保存数组的时候，由于L,R均会很大，不能直接存在数组中，要进行数组下标的移动。

然后数据还是有构造的，有些小地方要注意，标记在程序中了。

#include<bits/stdc++.h>
using namespace std;
int a[1000000],b[1000000],c[1000005];
int main()
{
	    int l,r;
        cin>>l>>r;
        if(l==1)
           l++;
		int rr=sqrt(r);
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(int i=2;i<=rr;i++)
		{
			if(a[i]==0)
			{
				for(int j=i;j<=rr/i;j++)
				    a[j*i]=1;
				int len; //找到一个len,保证len*i>=左边界l 
				if (l%i==0)
				    len=l/i;
				else
				    len=l/i+1;
				for(int j=len;j<=r/i;j++)
				//注意当l等于i时,len的值为1.
				//而我们设定的j,为i的若干倍，所以j的值不能为1，而是要大于1 
				  if (j>1)
				      b[j*i-l]=1;
			}
		}
		int minl,minr,minc=1e9,maxl,maxr,maxx=0,m=0;
		for(int i=l;i<=r;i++)
		{
			if(b[i-l]==0)
			   {
			   c[++m]=i;
			   }
			if (i==r)
			//注意r的值可能为2147483647,所以此时就应该要跳出循环
			//否则再执行i++后，其值变为负数 
			    break;
		}
		if(m<=1) 
		{
			cout<<"Not find"<<endl;
			return 0;
		}
		for(int i=2;i<=m;i++)
		{
			if(c[i]-c[i-1]<minc)
			{
				minc=c[i]-c[i-1];
				minl=c[i-1];
				minr=c[i];
			}
			if(c[i]-c[i-1]>maxx)
			{
				maxx=c[i]-c[i-1];
				maxl=c[i-1];
				maxr=c[i];
			}
		}
		cout<<minl<<" "<<minr<<" "<<maxl<<" "<<maxr<<endl;
	
	return 0;
}