POJ 2689 Prime Distance 埃拉托色尼筛法

发表于 | 分类于 | 阅读次数:
字数统计: 605 字

题目链接：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]);

	}
}