Prime Distance
题意：给一个区间，让你求出区间中间相邻最近和相邻最远的素数对。 L、R在int正数范围内。R-L<=1e6 思路：其实就一个区间筛的模板题。 区间筛什么意思呢？就是给的区间L，R都很大，但是R-L不是很大。 首先第一步，用线性筛法把sqrt（R）以内的素数都筛选出来。因为在区间R以内只要一个数不是素数，就一定能被sqrt（R）内的素数整除。 第二步，将第一步筛出来的素数，去遍历标记区间[L,R]的数。即标记筛出来的素数的倍数。这里的数组标记，因为R-L不大，所以我们可以把[L,R]映射到[0,R-L]。 第三步，没被标记的数字就是素数，遍历一下即可。
#include<iostream> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const int N=1e6+5; bool vis1[N],vis2[N]; ll p[N],q[N/10]; void Get_Prime(ll L,ll R){ memset(vis1,0,sizeof vis1); memset(vis2,0,sizeof vis2); p[0]=q[0]=0; ll sqR=sqrt(R)+1; for(ll i=2;i<=sqR;i++){ if(!vis1[i]){ p[++p[0]]=i; for(ll j=i*i;j<=sqR;j+=i){ vis1[j]=1; } } } for(int i=1;i<=p[0];i++){ ll left=L/p[i]*p[i]; while(left==p[i] || left<L) left+=p[i]; for(ll j=left;j<=R;j+=p[i]) vis2[j-L]=1; } if(L==1) vis2[0]=1; for(int i=0;i<=R-L;i++) { if(!vis2[i]){ q[++q[0]]=i+L; } } } int main(){ ll L,R; while(cin>>L>>R){ Get_Prime(L,R); if(q[0]<2) cout<<"There are no adjacent primes."<<endl; else{ ll ma=0,mi=2e9; ll x1,x2,y1,y2; for(int i=2;i<=q[0];i++){ if(q[i]-q[i-1]<mi){ x1=q[i-1]; y1=q[i]; mi=q[i]-q[i-1]; } if(q[i]-q[i-1]>ma){ x2=q[i-1]; y2=q[i]; ma=q[i]-q[i-1]; } } cout<<x1<<","<<y1<<" are closest, "<<x2<<","<<y2<<" are most distant."<<endl; } } return 0; }