[原创]POJ 2689 Prime Distance [筛法选取素数]【数论】

2016-09-16 14:01:15 Tabris_ 阅读数：677

博客爬取于2020-06-14 22:43:18
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52555267

题目链接：http://poj.org/problem?id=2689
-------------------------.
Prime Distance
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 16728 Accepted: 4450
Description

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).
Input

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.
Output

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.
Sample Input

2 17
14 17
Sample Output

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

---------------------------------------.

题目大意：
就是给定一个区间L,U∈[1,2147483647] U-L∈[1 000 000] 让你求出这个区间内距离最近和距离最远的两个素数对

解题思路 :
看似不难的题目因为给了[1,2147483647] 这么一个数据范围变得似乎不可解了
其实并不难 至少出题人还给了区间范围≤1 000 000 这么人性化的一个设定

我们考虑的事求出区间内的素数
其实也就是求出区间内的合数 剩下的就是素数了
这道题目显然不能用朴素的素数测试了 然后想到筛法 但是筛法并不能筛[1,2147483647] 这么大范围的素数
这时候根据朴素测试想到选取素数只需要选取其根号下的范围即可
这样范围就缩小到[1,(1<<16)] 这么小的范围了 然后筛法就行了

最后要确定的是[L,U]区间内的素数个数 同样 我们只要晒出合数就行了
筛的代码也很好实现

1
2
3
4
5
6
7
for(LL i=0; i<k; i++)
{
    b=l/prime[i];
    while(b*prime[i]<l||b<=1) b++;
    for(LL j=b*prime[i]; j<=r; j+=prime[i]) //注意这里的j一定要用LL  否则数据溢出会出现死循环...
        if(j>=l)    is_prime2[j-l]=false;
}

上述代码应该很好理解 就是找[1,(1<<16)] 范围内质数的倍数 也就是[L,U]范围内的合数 其实就是筛法选素数 一样的

然后遍历一下 把[L,U]内的素数记录下来
最后在遍历一下 找一下符合题意的素数对就行了

当然上述两行是可以在一次遍历中实现的 有兴趣的话 可以自己实现一下

附本题代码
--------------------------.

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
73
74
75
76
77
78
79
80
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back

# define lalal puts("*******");
/*************************************/

int prime[50050],k=0;
bool vis[(1<<17)+20];

void Prime(  )
{
    memset(vis,true,sizeof(vis));
    vis[0]=vis[1]=false ;
    int Max = (1<<17)+10;
    for (int i=2; i<=Max; i++)
    {
        if(vis[i])   prime[k++]=i;
        for(int j=0; j<k&&i*prime[j]<=Max; j++)
        {
            vis[i*prime[j]]=false;
            if (!( i % prime[j])) break;
        }
    }
}

bool is_prime2[1010101];
LL      prime2[1010101];
int main()
{
    Prime();
    LL l,r;
    while(cin>>l>>r)
    {
        memset(is_prime2,true,sizeof(is_prime2));
        LL b;
        for(LL i=0; i<k; i++)
        {
            b=l/prime[i];
            while(b*prime[i]<l||b<=1) b++;
            for(LL j=b*prime[i]; j<=r; j+=prime[i])
                if(j>=l)    is_prime2[j-l]=false;
        }


        int num=0;
        for(int i=0; i<=r-l; i++)
            if(is_prime2[i]&&i+l>=2) prime2[num++]=i+l;

        if(num<2)    printf("There are no adjacent primes.\n");
        else
        {
            LL minl,minr,maxl,maxr;
            LL mini=INF,maxi=-1;
            for(int i=1; i<num; i++)
            {
                if(prime2[i]-prime2[i-1]<mini)
                    minr=prime2[i],minl=prime2[i-1],mini=prime2[i]-prime2[i-1];
                if(prime2[i]-prime2[i-1]>maxi)
                    maxr=prime2[i],maxl=prime2[i-1],maxi=prime2[i]-prime2[i-1];
            }
            printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",minl,minr,maxl,maxr);
        }
    }
    return 0;
}