POJ 2689 Prime Distance 埃拉托色尼筛法

题目链接:http://poj.org/problem?id=2689

题意

给出一个区间[L,R],求这个区间内的连续两个素数之间的差最大和最小的两个素数,范围限制为1<=L< U<=2,147,483,647。但是所给的区间长度不会超过1000000。

题解

对于这个范围,全部筛选打表是不现实的,想到了只对区间内的素数进行筛选。这里用到了一个埃拉托色尼筛法的定理:如果n是一个合数,那么n一定有一个不超过sqrt(n)的素因子。这样我们只需要对前面5万个数的素数进行打表就行了。
枚举前面的素数,将对应区间内的合数进行删除,达到筛选的目的。同时计算素数对应到区间的倍数避免一个一个枚举,实现加速。
要注意新素数表中一些细节的处理,比如说排除值为1的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
const int maxn=1000003;
const int maxp=50050;
bool is_prime[maxp];
int prime[maxp],num;
bool is_prime2[maxn];
ll prime2[maxn],num2;
void prime_init()
{
num=0;
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2;i<maxp;i++)
{
if(is_prime[i]) prime[num++]=i;
for(int j=0;j<num && i*prime[j]<maxp;j++)
{
is_prime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}
void bigger_prime(ll L,ll R)
{
memset(is_prime2,1,sizeof(is_prime2));
ll mul;
for(int i=0;i<num && prime[i]<=R;i++)
{
if(prime[i]<=L)
mul=(L-prime[i])/prime[i]; //获得相差的倍数
else
mul=2;
while(mul*prime[i]<L || mul<=1) mul++; //修正倍数值,不能够等于一
for(ll j=mul*prime[i];j<=R;j+=prime[i])
if(j>=L)
is_prime2[j-L]=0;
}
num2=0;
for(int i=0;i<=R-L;i++)
{
if(is_prime2[i])
{
if(i+L==1) continue; //注意要排除1这个不是素数的数
prime2[num2++]=i+L;
}
}
}
void solve()
{
ll L,R;
prime_init();
while(scanf("%lld %lld",&L,&R)!=EOF)
{
bigger_prime(L,R);
ll maxv=0,minv=INF,maxid,minid;
for(int i=0;i<num2-1;i++)
{
if(maxv<prime2[i+1]-prime2[i])
maxv=prime2[i+1]-prime2[i],maxid=i;
if(minv>prime2[i+1]-prime2[i])
minv=prime2[i+1]-prime2[i],minid=i;
}
if(num2<2)
printf("There are no adjacent primes.\n");
else
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",prime2[minid],prime2[minid+1],prime2[maxid],prime2[maxid+1]);
}
}