质数距离

Prime Distance

题面

• 给定两个正整数 $l,r$，求 $[l,r]$ 间 相邻 的两个差最大的质数和 相邻 的两个差最小的质数。如果区间内质数个数 $\le 1$，输出 There are no adjacent primes.。
• $1\le l<r\le 2^{31}-1$，$r-l\le 10^6$。

样例 #1

样例输入 #1

2 17
14 17

样例输出 #1

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

思路

如果是 1e6 范围内, 直接线性筛求质数然后枚举所有相邻的质数对判断即可。

但这里是 $2^{31}-1$, 为 int 类型的最大值, 显然无法直接进行从 1 筛到头。

想个法子优化优化。可以发现我们要查询的区间还是只有 1e6, 那么若能求出来里面的所有质数, 就可以直接线性查询。

思考这样一个性质： 对于一个数 $n$, 它的质因子 $p$ 一定满足不等式 $p\le \sqrt{n}$, 数 $n$ 只能由相对于 $\sqrt{n}$ 一大一小两个因子相乘, 或者俩 $\sqrt{n}$ 相乘得出。

那么当我们想求 $l,r$ 的质因子时, 就可以先线性筛 $[1,\sqrt{n}]$ 的质数, 然后对于每个质数, 用欧拉筛的思路枚举该质数的倍数, 将结果筛掉即可。之后再枚举 $[l,r]$ 区间内的数, 把质数都放到一个数组 $primes[N]$ 中, 最后再根据该数组求解。

时间复杂度计算：

筛质数部分 $O(\sqrt{n})\approx O(46341)$

得出的质数个数可以用素数定理 $\pi (n)\approx \frac{n}{\ln n}$ 得出, 大约为 $\frac{46341}{\ln 46341}\approx 4314$ 个

用质数来筛掉 $[l,r]$ 区间时, 若当前质因子为 $p$, 可以直接从区间内最小的质因子倍数开始筛, 即 $\frac{l+p-1}{p}\times p$ (此时的除法是下取整), 注意该起点也必须至少大于 $p$ 。

而质因子 $p$ 在 $[l,r]$ 区间内的枚举其倍数的次数为 (设区间长度为n) $n\times (\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\dots )$, 分数和部分其级别是跟 $\log \log \sqrt{n}$ 同一级, 故这一步的时间复杂度大概是 $1e6\times \log \log \sqrt{1e6}\approx 1e6\times 3$ , 可以认为是 $O(n)$。

最后同样也是 $O(n)$ 扫描一遍, 故整体时间复杂度也是 $O(n)=O(1e6)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
// #define debug
const int N = 1e6 + 10, M = 5e4 + 10;
LL primes[N], cnt;
bool st[N];
LL l, r;
 
void init()
{
    memset(primes, 0, sizeof primes);
    memset(st, 0, sizeof st);
    cnt = 0;
    for (int i = 2; i <= M; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= M; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}
 
void solve()
{
    init();
    memset(st, 0, sizeof st);
    for (int i = 0; i < cnt; i++)
    {
        LL p = primes[i];
        for (LL j = max((l + p - 1) / p * p, p * 2); j <= r; j += p)
            st[j - l] = true;
    }
 
    cnt = 0;
    for (int i = 0; i <= r - l; i++)
        if (!st[i] && i + l >= 2)
            primes[cnt++] = i + l;
 
    if (cnt <= 1)
    {
        cout << "There are no adjacent primes." << endl;
        return;
    }
 
    int maxp = 0, minp = 0;
    for (int i = 0; i + 1 < cnt; i++)
    {
        int sub = primes[i + 1] - primes[i];
        if (sub > primes[maxp + 1] - primes[maxp])
            maxp = i;
        if (sub < primes[minp + 1] - primes[minp])
            minp = i;
    }
    printf("%d,%d are closest, %d,%d are most distant.\n",
           primes[minp], primes[minp + 1],
           primes[maxp], primes[maxp + 1]);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> l >> r)
    {
        solve();
    }
    return 0;
}