POJ 2689 Prime Distance (素数筛选法,大区间筛选)

时间:2023-03-08 17:55:29

题意:给出一个区间[L,U],找出区间里相邻的距离最近的两个素数和距离最远的两个素数。

用素数筛选法。
所有小于U的数,如果是合数,必定是某个因子(2到sqrt(U)间的素数)的倍数。
由于sqrt(U)最大也只有2^16,所以我们可以用素数筛选法,先预处理出2~2^16之间的素数,然后再用这些素数筛选出L~U之间的素数。
接着就好办了。

有几个要注意的是:
1:L为1的情况,可以通过令L=2或者标记isp[0]=false。
2:建议用long long,否则很容易在过程中超int范围,导致数组越界RE。。。

#include <iostream>
#include <cstdio>
#include <string.h> using namespace std;
const int maxn=(<<)+;
const int range=+;
bool isprime[maxn]; //标记2~2^16之间的素数
bool isp[range]; //标记L~U之间的素数,下标从0开始,对应L。
int prime[maxn]; //存储2~2^16之间的素数 int idx;
long long L,U; void init(){
idx=;
memset(isprime,true,sizeof(isprime));
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[idx++]=i;
for(int j=*i;j<maxn;j+=i)
isprime[j]=false;
}
}
}
int main()
{
init();
while(scanf("%I64d%I64d",&L,&U)!=EOF){
memset(isp,true,sizeof(isp));
if(L==)
isp[]=false; //忽略L为1了,导致测试样例1 2的时候,输出结果是1和2最近,1和2最远。
//筛选出L~U之间的素数
for(int i=;i<idx;i++){
int p=prime[i];
/*
这里我RE了好几次,原因如下:
1.j一开始定义成int型,导致j*p有可能超出int范围,变成负数,这样就使得j*p-L<0。
2.L一定要设成long long型,因为l+p-1可能会超int,变成负数。。。
*/
//这里的j表示的是p的倍数,j=(L+p-1)/p表示的是第一个大于等于L的倍数
for(long long j=(L+p-)/p;j*p<=U;j++){
if(j>){
isp[j*p-L]=false;
}
}
}
int mina,minb,mindis=,maxa,maxb,maxdis=;
int a,b;
bool first=true;
for(int i=;i<=U-L;i++){
if(isp[i]){
if(!first){
b=i;
if(b-a<mindis){
mina=a;
minb=b;
mindis=b-a;
}
if(b-a>maxdis){
maxa=a;
maxb=b;
maxdis=b-a;
}
a=b;
}
else{
first=false;
a=i;
}
}
}
if(!maxdis){
printf("There are no adjacent primes.\n");
}
else{
//注意:这里输出时long long格式,因为L是long long型
printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",mina+L,minb+L,maxa+L,maxb+L);
}
}
return ;
}