定理:任何一个合数n一定包含一个不超过$\sqrt{N}$的质因子
所以可以线性筛50000以内的质数,然后用质数去筛掉[l,r]区间内的合数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int primes[N],cnt;
bool st[N];
int l,r;
int prime[N],cntp; //prime存储[l,r]区间内的质数
bool st1[N];
void get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;i++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main(){
get_primes(50000);
while(cin>>l>>r){
memset(st1,false,sizeof(st));
for(int i=0;i<cnt;i++){
int p=primes[i];
for(ll j=max(((ll)l+p-1)/p*p,2ll*p);j<=r;j+=p){ //可能会溢出,必须开ll
st1[j-l]=true;
}
}
memset(prime,0,sizeof(prime));
cntp=0;
for(int i=0;i<=r-l;i++){
if(!st1[i]&&i+l>1){
prime[cntp++]=i+l; //1既不是质数也不是合数,所以i+l>1
}
}
if(cntp<2) cout<<"There are no adjacent primes."<<endl;
else{
int minp=0,maxp=0;
for(int i=0;i+1<cntp;i++){
int d=prime[i+1]-prime[i];
if(d<prime[minp+1]-prime[minp]) minp=i;
if(d>prime[maxp+1]-prime[maxp]) maxp=i;
}
printf("%d,%d are closest, %d,%d are most distant.\n", prime[minp], prime[minp + 1], prime[maxp], prime[maxp + 1]);
}
}
}