质数和约数
质数是指除了 \(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,?]\) 中的所有质数。
使用筛法求出 \([2,\sqrt{R}]\) 中的所有质数。
对于每个质数 \(?\) 把 ?, ? 中能被 ? 整除的数标记， 即标记 \(i \times p (\lceil \frac {L} {p} \rceil \le i \le \lfloor \frac {R} {p} \rfloor)\)为合数。
将筛出的质数进行相邻两两比较，找出答案即可。