POJ(2689 Prime Distance经典的区间筛选素数!)

spoiler posted @ 2011年5月02日 22:42 in 数论 , 1737 阅读

题目大意:给出一个区间,长度<=1000 000;求其中素数相邻素数之间的差最小的和最大的(左右端点的最值可以为2147483647);

题目分析:这里因为左右端点的数值过大,所以没办法用常规方法操作! 但是这里 区间的长度才1000000 这样的长度操作难度还是可以接受的 不会超时。

在这里我们先求出能表示2147483647的质因子 其实这个范围不大 就是sqrt(2147483647) 50000以内! 这里我着重解释一下为什么需要求2147483647? 举个例子说明,让你求一个区间a,b里相邻素数的最小、最大差值。
这里我们分两种情况讨论:

                         第一种:就是小数类型的a,b(也就是说b不大于2147483647里的最大质因子)

                                          这里我们只需要枚举,比较过去就可以了,不是吗?
                          第二种:a,b非常之大! 超过了2147483647里的最大质因数的值,这里我们该怎么办呢?

你会怎么做?第一我也跟你一样 ,真不知道如何转换, 您别灰心, 其实这里我们用到就是区间平移。何为区间平移?:就是把在长度为1000000的数组里进行模拟,下标为0的位置上的值   表示a的状态(就是指他是不是素数,"false"代表不是,反之则是素数!),下标为i上的值 表示 a+i  是否为素数!

然后要怎么做呢? 这里其实想通了 就好理解了,任何数都能用素数表示,对吗?如果这个数 不是任何比他小的素数的倍数(这里1没算素数),那么他肯定是素数,有木有?这样的话就好办了,我们只要把用来模拟平移的区间里,所有是2147483647的质因子的倍数全部筛选掉不就行了么?这里还补充一点 为什么是2147483647里面的质因子呢?因为你a,b肯定是比2147483647小,对吧?他的质因子肯定能够包含你的,所以用他的进行筛选,才是完整的满足任何一个在2147483647里面的大数。

这里我格外对代码和注意的地方强调一下!:

第一:for(i=1;i<=k;i++){
                start=l/pri[i]*pri[i];
                if(start<l)
                    start+=pri[i];
                start-=l;
                for(j=start;j<=end;j+=pri[i])
                    res[j]=false;    
            }// l 是(L)的小写形式

这是什么意思呢?start=l/pri[i]*pri[i]

                       就是求出最接近l的 start 能够整除pri[i]的数

                    例如 l=5;pri[i]=3;

                start=l/pri[i]*pri[i] 之后start=3;

               如果 start<l

                    那么start+=pri[i]

                          这里start=6了

             6是不是最接近5 并且能够整除3 的呢?

           懂了吗 ?如果不懂 您就留言吧

还有 一个注意的地方:

这里1不是素数,所以当输入的数第一个为1的时候 要自行加上一个1!不然就是错误的!

代码+注释:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool flag[1000001]={0};
int ans[1000001];
int pri[50000];
bool res[1000001];
int k;
void init(){
	int i;
	k=1;
	pri[1]=2;
	for(i=4;i<=50000;i+=2)
		flag[i]=1;
	for(i=3;i<=50000;i+=2){
		if(!flag[i]){
			pri[++k]=i;
			for(int j=2*i;j<=5000;j+=i)
				flag[j]=1;
		}	
	}
	return ;
}
void solve(){
	int i,j,times;
	long  sn1,en1,dis,mind,maxn,l,u,sn2,en2;
	long start,end;
	while(scanf("%ld %ld",&l,&u)!=EOF){
		end=u-l;
		if(l==1)
			l++;
		if(u<pri[k]){
			times=0;
			for(i=l;i<=u;i++)
				if(!flag[i])
					ans[++times]=i;
		}
		else{
			for(j=0;j<=end;j++)
				res[j]=true;
			for(j=(l%2!=0);j<=end;j+=2)
				res[j]=false;
			for(i=1;i<=k;i++){
				start=l/pri[i]*pri[i];
				if(start<l)
					start+=pri[i];
				start-=l;
				for(j=start;j<=end;j+=pri[i])
					res[j]=false;	
			}
			times=0;
			for(i=0;i<=end;i++)
				if(res[i])
					ans[++times]=i+l;
                                     //这里记得复原 移动的区//间哦题目要求的是区间,所以您得记得复原区间哦
		}
		mind=2147483647;
		maxn=0;
		for(i=1;i<times;i++){
			if(mind>ans[i+1]-ans[i]){
				sn1=ans[i];
				en1=ans[i+1];
				mind=ans[i+1]-ans[i];
			}
			if(maxn<ans[i+1]-ans[i]){
				sn2=ans[i];
				en2=ans[i+1];
				maxn=ans[i+1]-ans[i];
			}
		}
		if(maxn==0){
			printf("There are no adjacent primes.\n");
			continue;
		}
		printf("%ld,%ld are closest, %ld,%ld are most distant.\n",sn1,en1,sn2,en2);
	}
}
int main(){
	init();
	solve();
	return 0;
}

                 

                 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter