poj2689 Prime Distance(质数)

poj

题意:给定整数L,R((1<=L,R<=2^{31},R-L<=10^6)),求闭区间[L,R]中相邻两个质数的差最大和最小分别是多少,输出这两对质数.

分析:注意到R-L的取值范围是我们能够接受的范围,想办法筛去[L,R]中所有合数.考虑先求出2~(sqrt R)内的所有质数,对于每个质数p,把[L,R]中能被p整除的数标记.最后没有被标记的数就是质数,然后只要枚举比较就行了.

然后还有一个小技巧就是把[L,R]移到[0,R-L]中来,不然数组接受不了.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1000001],b[1000001],v[1000001];
int n,m,l,r,minn,maxn;
int x,y,xx,yy;
void prime(){
    memset(v,1,sizeof(v));
    for(int i=2;i<=46340;i++)
        if(v[i]){
            a[++n]=i;
            for(int j=2;j<=46340/i;j++)
				v[i*j]=0;
        }
}
int main(){
    prime();
    while(cin>>l>>r){
        memset(v,1,sizeof(v));
        if(l==1)v[0]=0;
        for(int i=1;i<=n;i++)
	    for(int j=l/a[i];j<=r/a[i];j++){
        	if(a[i]*j-l<0)continue;
			if(j>1)v[a[i]*j-l]=0;
	    }
        m=0;
        for(int i=l;i<=r;i++){
            if(v[i-l])b[++m]=i;
            if(i==r)break;
        }
        minn=2147483647;maxn=0;
        for(int i=1;i<m;i++){
            int j=b[i+1]-b[i];
            if(j<minn){minn=j;x=b[i];y=b[i+1];}
            if(j>maxn){maxn=j;xx=b[i];yy=b[i+1];}
        }
        if(!maxn) cout<<"There are no adjacent primes."<<endl;
        else cout<<x<<","<<y<<" are closest, "<<xx<<","<<yy<<" are most distant."<<endl ;
    }
    return 0;
}