本文主要是介绍poj2689筛法应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：输入两个数字L，U，0<U-L<=1e6,1<=L<U<=2147483647，找到最近的相邻素数和最远的相邻素数。
完成这道题需要细心，读完题后我们可以找到解决问题的思路：由于”L and U (1<=L< U<=2,147,483,647)“，开一个2147483647的数组显然不能满足内存要求，又由于”The difference between L and U will not exceed 1,000,000.“，我们能够把数组长度设置为1e6+1，怎样筛去L，U间的合数呢？最大合数的质因子一定有小于U^0.5的，这样质因子小于5e4，故找到50000内的所有素数然后用它们可以删除所有的合数。（总不能先删除1---2147483647所有的合数再来干事儿吧~~）。为了更快，可以用快速筛选。对了，注意1的问题，还有删除L--U的合数时要设置好起点start 。
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
const unsigned int maxn=1e6+1;
bool tag[50001];
LL p[50001],cnt,N=50000; //找到50000以内的素数即可筛除所有的合数(5e4*5e4 = 2.5e9>int上界)
LL midprime[maxn]; // 仅仅存储U,L 之间的素数（不用bool[U-L]的思路来做，防止数组过大带来麻烦。）
void getprime()
{
cnt = 0;
for (int i = 2; i <= N; i++)//快速筛选
{
if (!tag[i]) p[++cnt] = i; // tag[i]==0 means primer.for (int j = 1; j <= cnt && p[j] * i <= N; j++){tag[i*p[j]] = 1;if (i % p[j] == 0)break;}
}
}
int main()
{getprime();LL L,U,i;while(~scanf("%lld%lld",&L,&U)){while(L<2)L++;memset(midprime,0,sizeof(midprime));for(i=1;i<=cnt;i++){ // clear composite number between L and U.LL start=L+(p[i]-L%p[i]); //start is a prime which is not less than Lif(L%p[i]==0)start-=p[i]; //4 17 : for p[i]=2, start=4if(start==p[i])start+=p[i]; // 2 17: for p[i]=2, start=4 ,4 8 ---are cleared//cout<<"p[i]= start = "<<p[i]<<" "<<start<<endl;for(LL j=start;j<=U;j+=p[i]){midprime[j-L]=1; // j is ont a prime}}//for(i=L;i<=U;i++)if(!midprime[i-L])cout<<i<<" "; cout<<endl;LL close=1e6+1,far=-1,A1=0,A2=0,B1=0,B2=0,mark=0,pre=0;for(i=L;i<=U;i++){if(!midprime[i-L]){if(mark){if(close>i-pre){close=i-pre;A1=pre; A2=i;}if(far<i-pre){far=i-pre;B1=pre; B2=i;}pre=i;}else {pre=i;mark=1;}}}if(!A2)printf("There are no adjacent primes.\n");else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",A1,A2,B1,B2);}return 0;
}这篇关于poj2689筛法应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
