0x10 质数
质数基本定理
-
质数的定义：只被 \(1\) 和它本身整除的正整数叫做质数。非质数的正整数叫做合数。特别的，\(1\) 既不是质数也不是合数。
-
质数的数量很少。
-
只有 \(2\) 是偶素数。
-
唯一分解定理：将一个正整数 \(n\) 分解质因数，有且只有一种方式。形如 $n = {p_1}^{c_1} {p_2}^{c_2} \dots {p_m}^{c_m} $。其中 \(p_i\) 是互不相同的质数。
质数判断
试除法判定质数
枚举 \(\le n\) 的每个数，复杂度 \(O(n)\)。
改进：枚举 \(\leq \sqrt{n}\) 的数，复杂度 \(O(\sqrt{n})\)。
证明：一个数的最小质因子一定小于等于 \(\sqrt{n}\)。
设 \(n = p \times q\)， \(p \leq q\) 。
\(p = \cfrac{n}{q} \leq \sqrt{n}\)
核心代码如下：
bool is_prime(int n)
{
if (n < 2) return false;
for (int i = 2; i <= n / i; i ++ )
if (n % i == 0)
return false;
return true;
}
分解质因数
枚举 \(1\) 到 \(\sqrt{n}\) 之间的每个质数，看看能不能整除 \(n\) 。复杂度 \(O(\sqrt{n})\) 。
实现上更加简单。大概不需要解释。
核心代码如下：
void find_factors(int n)
{
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0)
{
cout << i << ' ';
int cnt = 0;
while (n % i == 0)
cnt ++ , n /= i;
cout << cnt << endl;
}
}
if (n > 1) cout << n << ' ' << 1 << endl;
}
质数筛法
筛法的主要思想是快速求出某一范围内的所有质数。利用前面的质数判定，可以做到 \(O(n \sqrt{n})\) 的复杂度。然而这是远远不够的。我们需要线性或者略高于线性的算法。目前主要的筛法是埃氏筛法和欧拉筛法。
1. 埃氏筛法
当我们枚举到某个质数 \(p\) 的时候，我们把他所有的倍数 （$p \times 1, p \times 2 \dots $）都设成合数。剩余的就是质数。
由于唯一分解定理，每一个合数都可以被前面的某一个质数筛掉。这保证了算法的正确性。
下面分析一下复杂度：每个质数 \(p\) 可以筛掉 \(O(\left \lfloor \dfrac{n}{p} \right \rfloor)\) 个数。
这样复杂度就是 \(O(\prod_{p \in P}^{} \dfrac{n}{p})\)。而 \(\leq n\) 的质数大约有 \(\log n\) 个，\(\sum_{i = 1}^{n} \cfrac{1}{i} \approx \log n\)。因此复杂度大约为 \(O(n \log \log n)\)
核心代码如下：
void get_primes(int n) {
// is_prime 表示这个数是不是质数
// primes 表示质数集合
for (int i = 2; i <= n; i ++ ) {
if (!is_prime[i]) primes[ ++ cnt] = i;
else continue; // 小剪枝：不是质数不往后筛
for (int j = i + i; j <= n; j += i) // 枚举 i 的倍数并筛掉
is_prime[j] = true;
}
}
2. 欧拉筛法
埃氏筛法的弊端是：每个合数不仅仅只被一个数筛过。例如 \(6\) 就被 \(2, 3\) 筛过两次。
那么怎么确保每个数只被筛过一遍呢？思路在代码里了。
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[ ++ cnt] = i; // 如果这个数没有被标记为合数，则为质数
for (int j = 1; primes[j] * i <= n; j ++ ) // 枚举前面已经得到的质数去更新后面的，同时要保证 primes[j] * i <= n, 因为更新大于n的数就没有意义了
{
st[i * primes[j]] = true;
if (i % primes[j] == 0) break; // 小优化
/*
1. 当 i % primes[j] != 0时, 说明此时遍历到的 primes[j] 不是 i 的质因子，那么只可能是此时的 primes[j] < i 的
最小质因子,所以primes[j] * i的最小质因子就是primes[j];
2. 当有 i % primes[j] == 0 时,说明i的最小质因子是 primes[j] ,因此 primes[j] * i的最小质因子也就应该是
prime[j]，之后接着用 st[primes[j + 1] * i] = true去筛合数时，就不是用最小质因子去更新了,因为 i 有最小
质因子 primes[j] < primes[j + 1] ,此时的 primes[j + 1] 不是primes[j + 1] * i 的最小质因子，此时就应该
退出循环，避免之后重复进行筛选。
*/
}
}
}
由于每个数只被筛过一次，因此时间复杂度为 \(O(n)\)， 为线性复杂度。是目前已知最快的筛法。
其他
Miller_Rabbin 算法
\(Miller\text{_}Rabbin\) 算法是目前已知最快的质数判断算法。
要学习这个算法，首先要知道费马小定理：
对于任意一个素数 \(p\) 和任意与 \(p\) 互质的数 \(a\)，都有：
\[a ^ {p - 1} \equiv 1 (mod\ p) \]证明请自行百度。。。
那么通过这个柿子，我们是否可以得到，满足该柿子的数 \(p\) 一定是质数呢？答案是不可以。反例请自行查阅“卡迈克尔数”。
但是卡迈克尔数毕竟很少（在 \(10 ^ 18\) 范围内是很少的）,因此我们可以通过一些方法，降低错误概率。
首先说一下二次探测定理：若有
\[a ^ 2 \equiv 1 (mod\ p) \]则有 $$a ^ 2 - 1 \equiv 0 (mod\ p) \\ (a + 1)(a - 1) \equiv 0 (mod \ p) \\ (a + 1) \ mod\ p = 0 或 (a - 1)\ mod \ p = 0$$
因此 \(a = \pm 1\)
这样，如果有 \(a ^ {2t} \equiv 1 (mod \ p)\) 且 \(a^t \mod p \ne \pm 1\) （当然，这个 \(-1\) 应该表示成 \(a - 1\)），那么这个数就不是素数。（有上面的二次探测定理易得）。
那么，我们找到一个质数 \(a\)，让它变成 \(a ^ t, a ^ {2t}, a ^ {4t} \dots\)，只要有一个不满足上面提到的判断条件，就可以说明 \(p\) 不是质数。
据科学家统计，在 \(OI\) 中，极小的错误概率不会发生。
核心代码：
int test[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
bool is_prime(int p) {
if (p == 1) return false;
int k = 0, t = p - 1;
while (!(t & 1)) t >>= 1, k ++ ;
// 将 p - 1 拆成 2 ^ k * t 的形式
for (int i = 0; i < 9; i ++ ) {
if (p == test[i]) return true;
LL a = qpow(test[i], t, p), ne = a;
for (int j = 1; j <= k; j ++ ) {
ne = a * a % p;
if (ne == 1 && a != 1 && a != p - 1) return false;
a = ne;
}
if (a != 1) return false; // 费马小定理对 p 不成立也说明 p 不是质数
}
return true;
}