【题目大意】
给定一个区间[L,R]，求区间内的质数相邻两个距离最大和最小的。
【思路分析】
其实很简单呀，很明显可以看出来是数论题，有关于质数的知识。
要注意一下的就是L和R的数据范围都很大，所以直接跑出1～R的所有质数是不可能的，于是我们就要想办法cut掉一些时间了
然后发现跑出1～的所有质数是不会超时的，接下来就好办了，直接用这些质数去标记出[L,R]区间内的合数，这样就可以在规定时间内得到[L,R]区间内的质数了，把相邻两质数相减再比较一下就可以得出答案啦QWQ
【代码实现】
这里要说一个问题就是我也不知道为什么我打的代码会TLE掉，虽然我真的jio得和标程没啥差别，所以就一起放上来吧，要是有dalao发现了我的代码问题出在哪里麻烦告知O(∩_∩)O谢谢啦
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 int a[1000001],b[1000001];
7 bool v[1000001];
8 int n,m,i,j,t1,t2,x1,x2,y1,y2,l,r;
9 void prime(){//预处理:埃氏筛法筛素数
10 memset(v,1,sizeof(v));//初始值都是1,即一开始假设所有的都是质数
11 for(i=2;i<=46340;i++)
12 if(v[i]){//如果这个数没有被标记过,就说明是质数
13 a[++n]=i;//记录质数
14 for(j=2;j<=46340/i;j++) v[i*j]=false;
15 //把这个质数的倍数都标记为合数
16 }
17 }
18 int main(){
19 prime();
20 while(cin>>l>>r){
21 memset(v,1,sizeof(v));
22 if(l==1) v[0]=false;//如果没有这一步的话1会被当做质数处理
23 for(i=1;i<=n;i++)
24 for(j=l/a[i];j<=r/a[i];j++)
25 if(j>1) v[a[i]*j-l]=false;
26 m=0;
27 for(i=l;i<=r;i++){
28 if(v[i-l]) b[++m]=i;
29 if(i==r) break;
30 }
31 t1=2147483647;t2=0;
32 for(i=1;i<m;i++){
33 j=b[i+1]-b[i];
34 if(j<t1) {t1=j;x1=b[i];y1=b[i+1];}
35 if(j>t2) {t2=j;x2=b[i];y2=b[i+1];}
36 }
37 if(!t2) printf("There are no adjacent primes.\n");
38 else printf("%d,%d are closest, %d,%d are most distant.\n",x1,y1,x2,y2);
39 }
40 return 0;
41 }
介个是std
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 #define go(i,a,b) for(register int i=a;i<=b;i++)
7 using namespace std;
8 int L,R;
9 int prime[100002];
10 int v[100002];
11 bool prim[1000002];
12 int l,r,maxn=0,maxl,maxr,minn=1e6+2,minl,minr;
13 int main(){
14 int mid=46340;
15 int num=0;
16 go(i,2,mid){//这里我用的线性筛,和std不同
17 //但是线性筛不应该比埃氏要快吗？QAQ
18 if(v[i]==0){
19 v[i]=i;prime[++num]=i;
20 go(j,1,num){
21 if(prime[j]>v[i]||prime[j]>mid/i) break;
22 v[i*prime[j]]=prime[j];
23 }
24 }
25 }
26 /*go(i,2,mid){
27 if(v[i]==0){
28 prime[++num]=i;
29 go(j,2,mid/i) v[i*j]=1;
30 }
31 }*/
32 while(cin>>L>>R){
33 memset(prim,0,sizeof(prim));
34 maxn=0,minn=1e6+2,l=r=0;
35 if(L==1) prim[0]=1;
36 go(i,1,num)
37 go(j,1,R/prime[i]){
38 if(j*prime[i]<L) continue;
39 prim[j*prime[i]-L]=1;
40 }
41 int tot=0;
42 go(i,0,R-L){
43 if(prim[i]) {continue;}
44 if(l==0){l=i+L;tot=1;continue;}
45 r=i+L;tot++;
46 if(r-l>maxn) maxn=r-l,maxl=l,maxr=r;
47 if(r-l<minn) minn=r-l,minl=l,minr=r;
48 l=r;
49 }
50 if(tot<2) {printf("There are no adjacent primes.\n");}
51 else printf("%d,%d are closest, %d,%d are most distant.\n",minl,minr,maxl,maxr);
52 }
53 return 0;
54 }
介个是我的TLE代码