题目大意是对于给定的L，R，寻找在一个区间L，R中相邻质数的最大以及最小的情况。
因为给定的R范围比较大，因此无法直接进行一个预处理去执行相应的操作，而对应的R-L则比较小，因此我们可以从对应的R-L去下手
因此我们可以对区间里面的数字l~R去判断相对应的数字是不是质数，那么如何加快这个判断思路就是先预处理出来2~根号R的质数，若在区间里面的数字能被其标志，那么则去除
最终我们需要对L~R之间的数字进行一次处理即可
时间复杂度是o(根号RloglogR+（R-L）loglogR)
同时我们这里需要知道几个知识点
1.1不是质数
2.快速求质数的方法
快速求解质数可以用以下的方法
void get_primes(int n){ num = 0; memset(not_primes,0,sizeof not_primes); memset(primes,0,sizeof primes); for(int i = 2;i <= n;i++) { if(not_primes[i]) continue; primes[++num] = i; for(int j = i;j <= n / i;j++) not_primes[i * j] = 1; } }
在此之后，我们可以进行两边处理最后求解出我们需要的结果
#include <iostream> #include <cmath> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn = 1e6 + 10; typedef long long ll; ll primes[maxn]; ll not_primes[maxn]; ll res[maxn]; ll L,R; int num; void get_primes(int n){ num = 0; memset(not_primes,0,sizeof not_primes); memset(primes,0,sizeof primes); for(int i = 2;i <= n;i++) { if(not_primes[i]) continue; primes[++num] = i; for(int j = i;j <= n / i;j++) not_primes[i * j] = 1; } } void pre_primes(int n) { memset(res,0,sizeof res); if(L == 1) res[0] = 1; for(int i = 1;i <= num;i++) { int LL = max(L/primes[i],primes[i]); for(int j = LL;primes[i] * j <= R ; j++) { res[primes[i] * j - L] = 1; } } } int main() { while(scanf("%lld %lld",&L,&R)!=EOF) { int pr = sqrt(R); get_primes(pr); pre_primes(pr); ll maxp = 0; ll max1,max2; ll minp = maxn; ll min1,min2; ll pre,pnum=0; // for(ll i = L;i <= R;i++) printf("%lld %lld\n",i,res[i]); for(ll i = L;i <= R;i++) { if(res[i - L] == 0) { pnum++; if(pnum == 1) pre = i; else { if(i - pre > maxp) { maxp = i - pre; max1 = pre; max2 = i; } if(i - pre < minp) { minp = i - pre; min1 = pre; min2 = i; } pre = i; } } } if(pnum < 2) printf("There are no adjacent primes.\n"); else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",min1,min2,max1,max2); } return 0; }