2023 长郡暑期集训 DAY-2 数学

质数和约数

质数是指除了 \(1\) 和它本身之外没有其他因数的自然数。

质数判定

判定单个自然数是否为质数，可以使用试除法，在这里不多描述。

bool is_prime(int n){
    if(n < 2) return 0; // 如果n小于2，不是质数，返回0
    for(int i = 2; i <= n / i; i++) // 从2开始逐个尝试除数i，直到i大于n的平方根
        if(n % i == 0) return 0; // 如果i能整除n，说明n不是质数，返回0
    return 1; // 如果没有找到能整除n的除数，说明n是质数，返回1
}

此算法复杂度为 \(O(\sqrt {n})\)

而接下来介绍判断 \([L,R]\) 中质数的筛法。

Eratosthenes筛法 （埃氏筛法）

我们知道一个合数一定可以分解为 \(p \times s (s \neq 1)\) 的形式，其中 \(q\) 是质数，\(s\) 是倍数。

那么我们就可以枚举 \([L,R]\) 中的 \(p\)，对于每个 \(p\)，枚举 \(s\)，标记掉合数 \(p \times s\)，剩下的必然是质数，这就是埃氏筛法。

但是我们会发现，如果使用这样的埃氏筛法，有一些数字会被标记多次，如 \(6\)，会被 \(2\) 和 \(3\) 标记两次。

所以我们可以做出一个小小的优化：

对于素数 \(p\)，只枚举倍数 \(x \geq p\) 的数，因为如果 \(x < p\)，则 \(x\) 中一定有比 \(q\) 小的质因子，\(q \times s\) 会在前面筛选过程中被筛出。

还可以发现，在枚举的过程中，每次筛完后剩下的区间内第一个数一定是质数，原因同上。

所以枚举质数时不需要从 \(1\) 枚举到 \(n\)，只要考虑到 \([2,\sqrt {n}]\) 中的质数即可。

此算法时间复杂度为 \(O(loglogn)\)

bool p[MAXN]; // 布尔数组，用于标记数字是否为合数
p[0] = p[1] = 1; // 将0和1标记为合数，因为它们不是质数
for(int i = 2; i <= n; i++){
    if(p[i]) continue; // 如果当前数已经被标记为合数，则跳过，因为它不是质数
    for(int j = i; i * j <= n; j++){
        p[i * j] = 1; // 将当前数的倍数（p * s）标记为合数
    }
}

线性筛法

尽管上面的埃氏筛法已经经过优化，减少了重复枚举的次数，可是合数还是会被重复枚举。

而这里的线性筛法，顾名思义，它的时间复杂度是 \(O(n)\) 的。

怎么做到的？

线性筛法每个合数只被它的最小质因数标记，所以每个数最多只会被标记一次。

依次考虑 \(2 - n\)之间的每一个数 \(i\)。

如果 \(i\) 是质数，则将其保存到质数表中。

否则利用 \(i\) 和质数表中的 \(pri_j\) 筛去 \(i \times pri_j\)。

注意，筛的过程中要确保 \(pri_j\) 是 \(i \times pri_j\) 的最小质因子。

bool p[MAXN]; // 布尔数组，用于标记数字是否为合数
p[0] = p[1] = 1; // 特判，将0和1标记
for(int i = 2; i <= n; i++){
    if(!p[i]) pri[++cnt] = i; // 如果当前数字i是质数，则将其加入质数数组pri，并增加计数器cnt
    for(int j = 1; j <= cnt && i * pri[j] <= n; j ++){
        p[i * pri[j]] = 1; // 将当前数字i与质数数组中的质数相乘得到的倍数标记为合数
        if(i % pri[j] == 0) break; // 如果i能被pri[j]整除，则跳出内层循环，避免重复标记
    }
}

练习1：Prime Distance

\(\texttt {Prime Distance}\) \(\text {- 洛谷}\)

简要题面

• 给定两个整数 \(L,R\)， 求 \([L,R]\) 中相邻的两个差最大的质数和相邻的两个差最小的质数。

• \(1 \le L < R \le 2 ^ {31} - 1,R - L \le 10 ^ 6\)

解题思路

由于数据范围很大，无法生成 \([1,