首页 > 代码库 > poj2689：素数筛
poj2689：素数筛
题目大意，给定l和u，求区间[l,u]内的素数中，相邻两个差最大和最小的素数
其中 u的范围达到了2e9
本质上需要找出n以内的所有素数，使用筛法。
先保存50000(大于sqrt(2e9))内的所有素数，然后再去筛出区间[l,u]内的素数（题上给定l-u<=1000000）所以可以存下所有素数
又由素数分布定理 素数个数s(n)~n/lnn并不是很大，所以找到所有素数保存在prime[]中扫一遍即可得到答案
代码如下
#include<stdio.h>#include<string.h>#include <algorithm>using namespace std;#define N 100007bool isprime0[50000];int prime0[50000];long long prime[100000];bool isprime[1000010];int num0;int num;long long x,y;void setprime(){ num=0; for(int i=2;i<=50000;i++) { if(!isprime0[i]) prime0[num0++]=i; for(int j=0;j<num0&&prime0[j]*i<=50000;j++) { isprime0[i*prime0[j]]=1; if(!(i%prime0[j])) break; } }}void setprime1(){ memset(isprime,0,sizeof(isprime)); for(int i=0;i<num0;i++) { long long j=x/prime0[i]; while(j*prime0[i]<x) j++; for(j=j*prime0[i];j<=y;j+=prime0[i]) if(j/prime0[i]>1) isprime[j-x]=1; } if(x==1) isprime[0]=1; num=0; for(long long i=0;i<=y-x;i++) { if(!isprime[i]) prime[num++]=x+i; }}int main(){ setprime(); while(scanf("%I64d%I64d",&x,&y)!=EOF) { setprime1(); long long a,b,c,d; long long mi=10000000,ma=0; if(num<2) { puts("There are no adjacent primes."); continue; } for(int i=0;i+1<num;i++) { long long p=prime[i+1]-prime[i]; if(p<mi) { a=prime[i]; b=prime[i+1]; mi=p; } if(p>ma) { c=prime[i]; d=prime[i+1]; ma=p; } } printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a,b,c,d); } return 0;}
poj2689：素数筛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。