题目大意：选出区间L,R之间相邻素数中差值最大和最小的素数对
素数筛（线性筛）：
#include #include #include using namespace std; #define MAX 10000000long long su[MAX],cnt; bool isprime[MAX]; void prime() { cnt=1; memset(isprime,1,sizeof(isprime));//初始化 isprime[0]=isprime[1]=0;//0和1不是素数 for(long long i=2;i<=MAX;i++) { if(isprime[i]) su[cnt++]=i;//保存素数 for(long long j=1;j
思路：直接用素数筛会超时（int范围线性复杂度时间复杂度已经达到10e9），而区间间隔比较小，只有1e6，而且对于int范围内的合数来说，最小质因子必定小于2^16。所以可以进行二次筛素数，第一次对50000以内筛素数，第二次筛出L,R区间内素数即可。
代码：
#include #include #include #include using namespace std;#define INF 1e9#define maxn 50005#define maxm 100005int l,u;int su[maxn],isprime[maxn],f[maxm];int cnt=0;void prime(){ memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=0; for(int i=2;i<=maxn;i++) { if(isprime[i]) su[cnt++]=i; for(int j=1;j >l>>u) { if(l==1)l=2;//注意l=1 memset(f,0,sizeof(f)); for(int i=0;i 1) f[j*su[i]-l]=1; } int p=-1,max_ans=-1,min_ans=INF,x1,y1,x2,y2; for(int i=0;i<=u-l;i++)//暴力枚举 { if(f[i]==0) { if(p==-1) { p=i; continue; } if(max_ans i-p) { min_ans=i-p; x2=p+l;y2=i+l; } p=i; } } if(max_ans==-1)cout<<"There are no adjacent primes."<