首页 > 代码库 > Poj2689筛素数
Poj2689筛素数
题目大意:
给定一个区间l,r,求这个区间内相邻的质数中最近的两个和最远的两个.区间范围是1-2^31,区间的长度最多是10^6.
思路:
刚开始对筛选法的理解不深,不知道如何筛选任意一段区间的素数,看了题解恍然大悟,原来用的筛选法总是筛选从1-n的素数,对于为何这样筛选理解不深刻.说下1-n的筛选法,就是用一个数组is_prime[1..n]标记1-n中哪个是素数哪个不是,从2(第一个素数)开始扫描,所有2的倍数都不是素数,那么下一个素数是谁?就是我们向后从is_prime[]中找到的第一个是素数的数.然后用这个素数筛掉后面是它倍数的数.理解了这个原理之后,就可以提前处理一下一定范围内的素数,然后直接用这个范围的素数对给定的任意区间进行筛选就可以了.
针对这个题,最大范围是10^9,那么只要求出sqrt(2^31)内的所有素数就可以筛选任意一个区间的素数了。
这题对筛素数的理解提高不少.
下面是ac代码
1 #include <iostream> 2 #include <cstdio> 3 #include <math.h> 4 #include <stdlib.h> 5 #include <string.h> 6 using namespace std; 7 #define maxn 500005 8 #define maxl 10000005 9 bool is_prime[maxl];10 int main()11 {12 int prime[maxn];13 memset(is_prime,1,sizeof(is_prime));14 for(int i=2;i<=sqrt(500000);i++)15 if(is_prime[i])16 for(int j=i*2;j<=500000;j+=i)17 is_prime[j]=0;18 int t=0;19 for(int i=2;i<=500000;i++)20 if(is_prime[i]) {prime[++t]=i;}21 int L,U;22 while(~scanf("%d%d",&L,&U))23 {24 memset(is_prime,1,sizeof(is_prime));25 if(L==1) is_prime[0]=0;26 for(int i=1;i<=t;i++)27 {28 if(prime[i]>sqrt(U)) break;29 __int64 start=1ll*L/prime[i]*prime[i];30 if(start<L) start+=prime[i];31 for(__int64 j=start;j<=U;j+=prime[i]) {if(prime[i]!=j) is_prime[j-L]=0;}32 }33 int minlen1,minlen2,maxlen,minlen,maxlen1,maxlen2,prenum=-1;34 maxlen=-1;35 minlen=0x7fffffff;36 for(int i=0;i<=U-L;i++)37 if(is_prime[i])38 {39 if(prenum==-1) prenum=i;40 else41 {42 if(i-prenum>maxlen) {maxlen=i-prenum;maxlen1=prenum;maxlen2=i;}43 if(i-prenum<minlen) {minlen=i-prenum;minlen1=prenum;minlen2=i;}44 prenum=i;45 }46 }47 if(maxlen==-1||minlen==0x7fffffff) printf("There are no adjacent primes.\n");48 else49 printf("%d,%d are closest, %d,%d are most distant.\n",minlen1+L,minlen2+L,maxlen1+L,maxlen2+L);50 }51 return 0;52 }
Poj2689筛素数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。