质数的判定 & 筛法
E1_de5truct0r
·
2022-06-03 09:55:21
·
个人记录
一、质数的定义
如果一个整数只能被 1 和它本身整除，那么他就是质数，否则就是合数。例如，3、5、7 都是质数，而 9 除了 1 和 9 还有 3 这个因数，所以 9 是合数。
二、质数的判定
朴素判定
顾名思义，直接从 2 枚举到 n-1 一个一个判断这个数是否能被整除。单个判断的时间复杂度 O(n)，总时间复杂度为 O(n^2)，显然太慢了。
根号判断
显然，感性理解一下，若 n 有 m 组不同的因数 (a_1,b_1),(a_2,b_2),...(a_m,b_m)，每组的乘积都是 n，a_i \leq b_i，那么显然 \forall 1 \leq i \leq m,a_i \leq \sqrt n。这也就是说，n 最多有 \sqrt n 组不同的因数，即 2 \sqrt n 个因数，并且可以通过 1 - \sqrt n 的枚举得到。
所以我们直接把朴素算法的循环范围改成从 2 到 \sqrt n 枚举。单个的时间复杂度就是 O(\sqrt n)，总时间复杂度是 O(n \sqrt n)。
但是，如果给你一个特别特别大的质数，比如 10^{16} \leq P \leq 10^{18}，单个 O(\sqrt n) 判断也不行，你该怎么办？
这个时候，就有一个神奇的方法出现了——
Miller-Rabin 筛法
Miller-Rabin 算法，一种基于随机化的质数判断筛法，是基于对使用费马小定理逆命题的运用，但是添加了关于 卡米切尔数 这种特殊情况的优化。
算法思想太复杂了，告辞（）
Miller Rabin 对费马质数检测做了以下改进：
选取多个不同的 a 作为基进行检测。
在执行快速幂的过程中，检查 a 的幂变成 1 之前的那一步是否为 n-1。
以 561 为例，我们除了要检查 a^{560}\mod 561 是否等于 1 ，还要检查 a^{280}\mod 561 的情况，假如存在 a^{280} \mod 561 \neq 560 且 a^{560} \mod 561=1，则可以判断 561 不是质数。（注：561 是卡米切尔数 qwq）
这样，单次查询时间复杂度均摊就降到了 O(\log n) 左右（存疑，不知道怎么证明），便可以通过 10^{16} \leq P \leq 10^{18} 的毒瘤数据了。
三、质数筛法
但是，话说，谁闲的没事了会给你一个素数让你判断啊？大多数情况都是给你一堆素数。
越来越多的质数，我该怎么办？？越来越多的质数，我该怎么办？？越来越多的质数，我该怎么办？？越来越多的质数，我该怎么办？？越来越多的质数，我该怎么办？？
这个时候，如果还是 O(n \sqrt n) 去莽，就会出事了。擅长均摊复杂度的筛法就派上用场了。
朴素埃氏筛
埃氏筛，或者说叫 \bold{\text{Eratothenes}} 筛法，它的思路大致如下：
- 如果没有被打过标记，说明是质数，那么把 $i \times 2$ 到 $n$ 的所有 $i$ 的倍数都打一个不是质数的标记。
- 否则不进行任何操作。
这种算法对于 $1$ 至 $n$ 的所有数的判定，时间复杂度是 $O(n \log n)$ 的。至于证明，可能要用到黎曼函数之类的东西，我会单独写一篇文章总结一下，到时候再挂链接吧。
埃氏筛的一些优化
显然的，O(n \log n) 有的时候没法满足要求。我们考虑进一步优化埃氏筛。
我们发现，加入当前枚举的是质数 i，那么显然 2 \times i 到 (i-1) \times i 的质数已经分别被 2 到 i-1 的质数筛过一遍了。所以我们第二重循环直接从 i 开始枚举即可。这样，时间复杂度就降到了 O(n \log \log n)。这个证明我太菜了，不会 /kk
线性筛！
对于任何的埃氏筛，不管怎么优化，总是会有一个数 p 同时被好几个质数筛到的情况。所以我们考虑怎么保证每一个数 p 只被一个数筛到。
那么我们就可以让 p 的最小质因子筛掉 p。也就是说直接记录所有的质数，每次看一下，顺便把不是素数的记录一下。这样就避免了重复，复杂度就是 O(n) 的了。
四、质因数分解
朴素分解
朴素分解应该很好想吧，因为 n 大于 \sqrt n 的质因数最多一个，所以直接 2 到 \sqrt n 枚举即可，每次如果 n 能整除 i 就一直除下去，直到不能整除为止。这样就避免了找到合数的情况（大家自己想一想为什么！qwq）。当然，如果我们先筛出一个质数表，那么时间复杂度可以降至 O(\frac{\sqrt n}{\ln n})。其实这个速度已经很快了 qwq。
Phollard-Rho 算法
这种算法更加高效，但是难度很大，而且目前来看也没啥屁用（其实是我太菜了），有兴趣的童鞋可以自行 bdfs 或者看看 OI-wiki 上的讲解。