Prime Distance POJ - 2689 线性筛

时间:2021-06-05 15:26:00

一个数 $n$ 必有一个不超过 $\sqrt n$ 的质因子。

打表处理出 $1$ 到 $\sqrt n$ 的质因子后去筛掉属于 $L$ 到 $R$ 区间的素数即可。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int Range=50000;
const int N=1000000+233;
int f[N],vis[Range+233],prime[Range];
int cnt;
void get_prime(){
for(int i=2;i<=Range;++i){
if(!vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<=Range;++j){
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
int main(){
get_prime();
int L,U;
while(scanf("%d%d",&L,&U)!=EOF){
memset(f,0,sizeof(f));
if(L==1)L=2;
for(int i=1;i<=cnt;++i){
int a=L%prime[i]==0?L/prime[i]:L/prime[i]+1;
int b=U/prime[i];
for(int j=a;j<=b;++j)if(j>1)f[j*prime[i]-L]=1;
}
int p=-1,x1,x2,maxans=-1,minans=N,y1,y2;
for(int i=0;i<=U-L;++i)
if(f[i]==0){
if(p==-1){p=i;continue;};
if(maxans<i-p){maxans=i-p,x1=p+L,x2=i+L;}
if(minans>i-p){minans=i-p,y1=p+L,y2=i+L;}
p=i;
}
if(maxans==-1)
cout<<"There are no adjacent primes."<<endl;
else cout<<y1<<","<<y2<<" are closest, "<<x1<<","<<x2<<" are most distant."<<endl;
}
return 0;
}