质数距离《算法竞赛进阶指南》

$质数距离《算法竞赛进阶指南》$

题目地址：196. 质数距离 - AcWing题库

题面

给定两个整数 $L$ 和 $U$，你需要在闭区间 $[L,U]$ 内找到距离最接近的两个相邻质数 $C_1$ 和 $C_2$（$C_1<C_2$）（即 $C_2?C_1$ 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数 $D_1$ 和 $D_2$（$D_1<D_2$）（即 $D_2?D_1$ 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数 $L$ 和 $U$，其中 $L$ 和 $U$ 的差值不会超过 $10^6$。

输出格式

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

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

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

数据范围

$1\le L<U\le 2^{31}?1$

输入样例：

2 17
14 17

输出样例：

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

思路

本题为多实例。

每次给出一个区间$[l,r]$，然后求区间内的质数中，相邻且差值最大和差值最小的两组质数。

1. 由于数据范围很大，我们无法通过线性筛法来把区间内的质数筛出来。本题结束
2. 因此我们需要思考一下质数的相关定理：任何一个大于1的正整数都能唯一分解为有限个质数的乘积。
3. 所以我们可以先求出50000以内的质数，然后找出区间中能整除这些质数的数字并去掉，这样区间$[l,r]$中剩下的数字就全为质数。

具体做法如下，但需要注意几个问题：

1. 计算过程中会爆int。
2. 对于质数$x$，我们需要将区间内$x$的倍数全部去掉，因此需要找到大于$l$且为$x$的倍数的最小数：$\frac{l+x?1}{x}\times x$

标程

vector<int> p(N);
bool q[N];
int tot;

void primes(int n) {
    for(int i = 2; i <= n; i ++ ) {
        if(!q[i]) p[tot++] = i;
        for(int j = 0; p[j] <= n / i; j ++ ) {
            q[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

void Solved() {
    LL l, r;
    primes(50000);			//预处理出50000以内的质数
    while(cin >> l >> r) {
        int mi = INF, mx = -1;
        vector<int> a;
        memset(q, false, sizeof q);	//重复利用，更加环保
        for(int i = 0; i < tot; i ++ ) {
            //从大于l的最小的p[i]的倍数开始枚举
            for(LL j = max(2ll * p[i], (l + p[i] - 1) / p[i] * p[i]); j <= r; j += p[i] ) {
                q[j - l] = true;	//数太大了，需要减去l这个偏移量
            }
        }
        
        for(int i = 0; i <= r - l; i ++ )				//统计区间的质数
            if(!q[i] && i + l > 1) a.push_back(i + l);	//记得把偏移量l加回来

        if(a.size() < 2) {
            cout << "There are no adjacent primes.\n"; continue;
        }
        for(int i = 0; i < a.size() - 1; i ++ ) {
            int x = a[i + 1] - a[i];
            if(x < a[mi] - a[mi - 1]) mi = i;
            if(x > a[mx] - a[mx - 1]) mx = i; 
        }
        cout << a[mi] << "," << a[mi + 1] << " are closest, ";
        cout << a[mx] << "," << a[mx + 1] << " are most distant.\n";
    }
}