思想:
用到了欧拉筛,然后对数组的内存的巧妙处理。
推荐的博客:
https://blog.csdn.net/Feynman1999/article/details/79533130?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
推荐的b站:
https://www.bilibili.com/video/av89230175?from=search&seid=1935489020745550394
代码:
#include<iostream> #include<stdio.h> #include<vector> using namespace std; const int maxn = (1<<16)+10; bool valid[maxn]; int ans[maxn]; bool vis[maxn<<4]; int tot; void get_prime(int n){ tot = 0; for(int i=2;i<=n;i++) valid[i] = true; for(int i=2;i<=n;i++){ if(valid[i]) ans[++tot] =i; for(int j=1;j<=tot&&ans[j]*i<=n;j++){ valid[ans[j]*i] = false; if(i%ans[j]==0) break; } } } int main(){ get_prime(1<<16); int L,R; while(cin>>L>>R){ for(int i=1;i<=(R-L+1);i++) vis[i] = true; if(L==1) vis[1] = false; for(int i=1;i<=tot;i++){ for(int j=max(ans[i],(L-1)/ans[i]+1);j<=R/ans[i];j++){ vis[ans[i]*j-L+1] = false; } } int num = 0; for(int i=1;i<=(R-L+1);i++) if(vis[i]) num++; if(num>=2){ vector<int>tep; for(int i=1;i<=(R-L+1);i++){ if(vis[i]) tep.push_back(L+i-1); } int ans1 = 0,ans2 = 0; int maxx = tep[1] - tep[0],minn = tep[1]-tep[0]; for(int i=2;i<tep.size();i++){ if(tep[i]-tep[i-1]>maxx){ ans2 = i-1; maxx = tep[i] -tep[i-1]; } if(tep[i]-tep[i-1]<minn){ ans1 =i-1; minn = tep[i] - tep[i-1]; } } cout<<tep[ans1]<<","<<tep[ans1+1]<<" are closest, "<<tep[ans2]<<","<<tep[ans2+1]<<" are most distant."<<endl; } else{ cout<<"There are no adjacent primes."<<endl; } } return 0; }