POJ 2689（素数+类区间筛法）

#include<iostream> #include<cmath> #include<string.h> #include<algorithm> #include<iomanip> #include<cstdio> #include<string> #include<map> #include<vector> typedef long long ll; using namespace std; bool mark[1000010]; bool p[50000]; ll prime[50000]; ll number[1000010]; int main() { ll cnt =0; memset(p,1,sizeof(p)); p[0]=p[1]=0; for(ll i=2;i<=50000;i++) { if(p[i]) { prime[cnt++]=i; for(ll j=i*i;j<=50000;j+=i) p[j]=0; } } ll l,r; while(cin>>l>>r) { memset(mark,1,sizeof(mark)); if(l==1) l=2; //从1开始的话把1筛不掉 for(ll i=0;prime[i]*prime[i]<=r;i++) { ll k=l/prime[i]; while(k*prime[i]<l) k++; if(k==1) k++; for(ll j=k*prime[i];j<=r;j+=prime[i]) mark[j-l]=0; } ll pcnt=0; for(ll i=l;i<=r;i++) if(mark[i-l]) number[pcnt++]=i; if(pcnt==1) cout << "There are no adjacent primes." << endl; else { ll ans1=0,ans2=0; for(ll i=0;i<pcnt-1;i++) { if(number[i+1]-number[i]>number[ans1+1]-number[ans1]) ans1=i; if(number[i+1]-number[i]<number[ans2+1]-number[ans2]) ans2=i; } cout << number[ans2] << ',' << number[ans2 + 1] << " are closest, " << number[ans1] << ',' << number[ans1 + 1] << " are most distant." << endl; } } return 0; }