196. 质数距离(素数筛)

╰半夏微凉° 2021-10-29 09:26 386阅读 0赞

题目链接:https://www.acwing.com/problem/content/description/198/  
[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
给定两个整数L和U，你需要在闭区间\[L,U\]内找到距离最接近的两个相邻质数C1和C2（即C2-C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1和D2（即D1-D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。  
输入格式

每行输入两个整数L和U，其中L和U的差值不会超过1000000。  
输出格式

对于每个L和U ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。  
数据范围

1≤L<U≤231−1

输入样例：

2 17  
14 17

输出样例：

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

分析:  
直观思路，暴力筛。  
可是数据范围太大了。  
又得知R-L的范围较小。于是想通过此得到结论。  
我们考虑一些新的方法。对于L——R，这里面的合数，必定都包含一个不超过sqrt（R）的因子。那么我们，可以先求出（1——sqrt（R））中所有的素数。并标记L到R中所有的合数。然后可得结论。在标记的时候，我们需要注意一些地方，具体见代码:

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int L,U;
    int prime[101010],top;
    int id[1010101];
    
    void Prime(int R)
    {
        printf("%d\n",R);
        memset(id,0,sizeof(id));
        for(int i = 2; i <= sqrt(R); i ++)
        {
            if(id[i] != 0)
                continue;
            prime[++ top] = i;
            id[i] = i;
            for(int j = 1; j <= top; j ++)
            {
                if(prime[j] > id[i] || prime[j] * i > sqrt(R))
                    break;
                id[i * prime[j]] = prime[j];
            }
        }
        memset(id,0,sizeof(id));
        if(L == 1)//L为1的时候，id[0]的标记就要先打成1。否则出错。
            id[0] = 1;
        for(int i = 1; i <= top; i ++)
        {
            int x = L / prime[i];
            if(L % prime[i])
                x ++;
            int y = U / prime[i];
            for(int j = x; j <= y; j ++)
            {
                if(j != 1)//如果j==1，表示这个素数就在（L到R）的范围内，肯定不需要标记
                    id[j * prime[i] - L] = 1;
            }
        }
    }
    
    int main()
    {
        while(~scanf("%d%d",&L,&U))
        {
            Prime(U);
            int x = U - L;
            int far_x = -1,far_y = -1,min_x = -1,min_y = -1;
            int dis = 1e9,pre = -1;
            for(int i = 0; i <= x; i ++)
            {
                if(id[i] == 1)
                    continue;
                if(far_x == -1)
                    far_x = i + L;
                else
                    far_y = i + L;
                if(pre == -1)
                {
                    pre = i + L;
                    continue;
                }
                if(dis > i + L - pre)
                {
                    dis = i + L - pre;
                    min_x = pre;
                    min_y = i + L;
                }
                pre = i + L;
            }
            if(far_y == -1)
                printf("There are no adjacent primes.\n");
            else
                printf("%d,%d are closest, %d,%d are most distant.\n",min_x,min_y,far_x,far_y);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/