POJ（2689 Prime Distance经典的区间筛选素数！）
题目大意：给出一个区间，长度<=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;
}
评论 (0)