二次筛法

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

分析：本题数据区间的上界达到21亿，不能将所有小于21亿的素数存下来，只能针对本题的假设：区间长度小于1000000，把给定区间[ L,U ]的所有素数通过筛法找出来，使用筛法筛掉[L,U]区间的所有非素数，需要知道[L,U]区间的所有非素数的素数因子（因为一个非素数是被它的最小素数因子筛掉），2147483647内的数或者是素数，或者能被sqrt(2147483647)内的素数整除，也就是说，[L,U]区间的所有非素数的素数因子都在sqrt(2147483647)内，预先将sqrt(2147483647)内的所有素数找出来，然后用这些素数去筛掉指定区间的所有非素数。

代码：

#include 
#include 
#define N 50001
#define INF 99999999
long long prime1[N+2],nprime1;
bool isprime[20*N+2];
void make_prime1()
{long long i,j;nprime1=0;memset(isprime,1,sizeof(isprime));for(i=2;i=L){isprime[j-L]=0;}}if(L==1){isprime[0]=0;}}
}void solve()
{long long i;long long min=INF,max=-INF;long long minl,minr,maxl,maxr;make_prime2();nprime2=0;for(i=0;i<=U-L;i++){if(isprime[i]){nprime2++;prime2[nprime2]=i+L;}}if(nprime2<=1){printf("There are no adjacent primes.\n");}else{for(i=1;imax){max=prime2[i+1]-prime2[i];maxl=prime2[i];maxr=prime2[i+1];}}printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",minl,minr,maxl,maxr);}
}
int main()
{make_prime1();while(~scanf("%I64d%I64d",&L,&U)){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！