坑爹的解说,一点都不详细。。害我想好久。。
poj--2689
题意 找一个范围内的 相邻的 差 最小和最大 的 两个素数!
因为这个范围的上限值可能到了 int 的最大值。
所以直接用一次筛出全部素数 肯定超时,数组也开不到20多亿!
所以这里接触到 二次筛法!!
因为 范围 (L, U)其里面的合数的 一个素因子不可能 超过 sqrt(U)。-------PS:这个与我们判断一个数是否为 素数
原理一样,当一个数是合数时 它肯定是两个以上素因子的乘积,那么sqrt(X)以内肯定有一个素因子,那么只要找到它就可以
证明X为合数!
那么一样的道理,sqrt(U)以内的素数 一定可以把 这个范围内的合数全部 筛出来!
因为(L, U)范围里的合数,其至少有一个素因子 小于或等于 sqrt(U).
那么现在 就可以把 20多亿 开根号了!大约就是50000 了!规模减少很多!
综上所述:简单的说 就是先筛出50000内的素数,然后拿这些素数再去 筛出这个指定范围内的素数!
解释下面为什么J要大于1;因为前面对L/prime[i] 进行了
ceil取整处理,它得到整数是比原来大或等于的。。
所以当j=1时,其实这个值已经小于了(L,U)这个范围。
//Accepted 1236K 32MS C++ 1866B 2014-01-25 21:59:01 //Accepted 1256K 16MS C++ 1970B 2014-01-25 22:44:56 #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define N 50000 #define len 1000000//题目说了区间大小.不然若真是1到20亿,那么数组存不下这么多合数! #define inf 0x7fffffff using namespace std; bool isprime[N+5]; __int64 prime[N],cnt; bool res[len+5]; void init()//筛选50000 内的素数,要注意i比较大时会容易超int的范围 { __int64 i,j; cnt=0; memset(isprime,true,sizeof(isprime)); for(i=2;i<=N;i++) { if(isprime[i]) { prime[cnt++]=i; for(j=i*i;j<=N;j+=i) { isprime[j]=false; } } } } int main() { __int64 L,U,i,j,k,min,max,s,t; init(); while(scanf("%I64d%I64d",&L,&U)!=EOF) { memset(res,0,sizeof(res)); for(i=0;i<cnt;i++)//筛选区间内的素数 { if(prime[i]>U) break; s=(__int64)ceil((double)L/(double)prime[i]);//这里一定要注意取整,不然后面j*prime[i]-L t=U/prime[i]; //时就有可能出现负数! for(j=s;j<=t;j++) if(j>1)//凡是大于1的都是能够被这个素数整除的,即合数. res[j*prime[i]-L]=true; //-L是为了得到相对大小,其实也可以直接用(L,U). } k=-1,min=inf,max=-1;//k是为了保存前一个素数的值,以便计算相邻素数的差! __int64 dis,m1,m2; for(i=0;i<=U-L;i++)//最优值求解....长度为U-L { if(!res[i]) { if(k!=-1) { dis=i-k; if(dis>max) { max=dis; m1=i; } if(dis<min) { min=dis; m2=i; } } if(i+L!=1)//注意1的时候特殊判断1不是素数 k=i; } } if(max==-1)//无解的情况 { printf("There are no adjacent primes.\n"); } else { printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",m2- min+L,m2+L,m1-max+L,m1+L); } } return 0; }