POJ2689 Prime Distance 区间筛素数
Input
Output
Sample Input
2 17 14 17
Sample Output
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; const int maxn = 1000005; bool is_prime[maxn]; bool is_prime_small[maxn]; ll prime[maxn]; ll prime_num=0; //对区间[a,b)内的整数执行筛法,is_prime[i-a]=true --- 表示i是素数 注意这里下标偏移了a,所以从0开始。 void segment_sieve(ll a,ll b) { for(ll i=0;i*i<=b;++i) is_prime_small[i]=true; //对[2,sqrt(b))的初始化全为质数 for(ll i=0;i<=b-a;++i) is_prime[i]=true; //对下标偏移后的[a,b)进行初始化 for(ll i=2;i*i<=b;++i) { if(is_prime_small[i]) { for(ll j=2*i;j*j<=b;j+=i) is_prime_small[j]=false; //筛选[2,sqrt(b)); //(a+i-1)/i得到最接近a的i的倍数,最低是i的2倍,然后筛选 for(ll j=max(2LL,(a+i-1)/i)*i;j<=b;j+=i) is_prime[j-a]=false; } } for(ll i=0;i<=b-a;++i) //统计个数 if(is_prime[i]) prime[prime_num++]=i+a; } int main() { ll a,b,ans1,ans2,ans3,ans4,dis1,dis2; while(~scanf("%lld%lld",&a,&b)) { if(a==1) a++; prime_num=0; dis1 = 0; dis2 = 1000010; memset(prime,0,sizeof(prime)); segment_sieve(a,b); for(ll i=1;i<prime_num;++i) { //printf("%d",prime[i]); if(prime[i]-prime[i-1]>dis1) { dis1 = prime[i]-prime[i-1]; ans1 = prime[i-1]; ans2 = prime[i]; } if(prime[i]-prime[i-1]<dis2) { dis2 = prime[i]-prime[i-1]; ans3 = prime[i-1]; ans4 = prime[i]; } } //cout<<prime_num<<endl; if(dis1==0) printf("There are no adjacent primes.\n"); else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",ans3,ans4,ans1,ans2); //printf("%lld\n",prime_num); } return 0; }优质内容筛选与推荐>>