POJ 2689 Prime Distance 素数筛选 -

题目地址：http://poj.org/problem?id=2689

思路来源：http://blog.csdn.net/w20810/article/details/43313261

#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
vector<int> primes;
bool isPrime[1000000+5];
void getPrime()
{bool isPrime[46355];  //第一次筛选，求 1~sqrt(2,147,483,647)的素数 LL n=46350;memset(isPrime,true,sizeof(isPrime));for(int i=2;i<=n;i++) if(isPrime[i]){primes.push_back(i);if(i<=(LL)sqrt(n))for(LL j=i*i;j<=n;j+=i) isPrime[j]=false;}
}
void init(LL s,LL e)  //第二次筛选 ，求s~e中的素数
{memset(isPrime,true,sizeof(isPrime));for(int i=0;i<primes.size();i++)  //用第一次筛选出的素数求s~e的素数 {LL n=s/primes[i];            //为了让n*primes[i]大于s while(n<=1||n*primes[i]<s) n++;   for(LL j=n*primes[i];j<=e;j+=primes[i])if(j-s>=0) isPrime[j-s]=false; } 
} 
int main()
{LL s,e;getPrime();while(scanf("%lld%lld",&s,&e)!=EOF){LL mu,mv,cu,cv,p=0,ct=e-s+1,mt=0;if(s==1) s++;      //注意一定要加这一步 init(s,e);for(LL i=s;i<=e;i++){if(!isPrime[i-s]) continue;if(p==0);else {if(ct>i-p) cu=p,cv=i,ct=i-p;if(mt<i-p) mu=p,mv=i,mt=i-p;} p=i;}if(mt==0) cout<<"There are no adjacent primes."<<endl;else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",cu,cv,mu,mv);}return 0;
}