基础数学算法-质数距离

题目-质数距离

问题分析

因为$U$的范围是$2^{31}-1$级别的, 筛质数算法时间复杂度最优$O(n)$, 没办法在规定时间内处理所有的质数, 并且线性筛法只能从$2$开始筛, 不能只筛一个区间

注意到, $R-L\le 10^6$, 长度很小, 需要对筛法进行改进, 对于一个数的因子对$[d,\frac{n}{d}]$, 假设$d\le \frac{n}{d}$, 一个数的任意因子对$[d,\frac{n}{d}]$ , 一定存在$d\le \sqrt{n}$

算法步骤

1. 找出$[1,\sqrt{n}]$的质因子, 大概是$5\times 10^4$级别
2. 对于$[L,R]$中的合数, 一定存在质因子在$[1,\sqrt{n}]$之间, 将$[L,R]$之间质因子的倍数筛掉
3. 对于$[L,R]$枚举质数之间的距离统计答案

$\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+...+\frac{n}{\sqrt{n}}=n\log \log \sqrt{n}$
算法时间复杂度$O(\sqrt{n}+n\log \log \sqrt{n})$

计算$\ge l$最小的$p$的倍数, 也就是计算$\lceil \frac{l}{p}\rceil \times p$
利用等式$\lceil \frac{l}{p}\rceil =\lfloor \frac{l+p-1}{p}\rfloor$, 分情况讨论, 如果$l|p$, 相当于没加, 如果$l$不是$p$的倍数, $l\mathrm{mod}p=r$, $r\ge 1$, 因此结果会$+1$, 也就是达到了上取整的效果

代码实现

注意: val的值可能会爆$int$, 需要开$longlong$

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e6 + 10, M = 50010;

int l, r;
int primes[N], cnt;
bool st[N];

void init(int k) {
   
    for (int i = 2; i <= k; ++i) {
   
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= k / i; ++j) {
   
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void solve() {
   
    memset(st, false, sizeof st);
    cnt = 0;
    init(M);

    memset(st, false, sizeof st);
    for (int i = 0; i < cnt; ++i) {
   
        LL p = primes[i];
        LL val = max(2 * p, ((l + p - 1) / p) * p);
        for (LL j = val; 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 < 2) {
   
        printf("There are no adjacent primes.\n");
        return;
    }

    int minv = 0, maxv = 0;
    for (int i = 0; i < cnt - 1; ++i) {
   
        int d = primes[i + 1] - primes[i];
        if (d < primes[minv + 1] - primes[minv]) minv = i;
        if (d > primes[maxv + 1] - primes[maxv]) maxv = i;
    }

    printf("%d,%d are closest, %d,%d are most distant.\n", primes[minv], primes[minv + 1], primes[maxv], primes[maxv + 1]);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> l >> r) solve();

    return 0;
}