质数
定义：
若正整数 $a$ 的约数只有 $1$ 和 $a$，则称 $a$ 是质数。特殊地，$1$ 不是质数。
质数又称素数。
性质：
互质：
质数和除它倍数外的任意整数互质。
哥德巴赫猜想：
任一大于 $2$ 的偶数都可写成两个质数之和。
费马小定理：
对于质数 $p$ 和任意满足 $p\not\mid a$ 的整数 $a$，$a^{p-1}\equiv 1\pmod p$。
费马小定理最大的应用是求逆元，对于满足费马小定理的整数 $a,p$，$a\times a^{p-2}\equiv 1\pmod p$，所以 $a$ 的逆元就是 $a^{p-2}$，通常结合快速幂即可在 $O(\log n)$ 的时间内解决。
质数密度：
用 $\pi(n)$ 表示 $[1,n]$ 中的质数个数。
$\pi(n)\approx \dfrac{n}{\ln n}$，即：通常认为质数个数为 $O(\dfrac{n}{\log n})$ 级别的。
质数距离：
由质数密度容易猜想，任意两个质数之间的非质数数量不会特别多。
事实也确实如此，所以若要寻找比 $x$ 大的最小质数，可以暴力向后枚举判断是否是质数。
唯一分解定理：
任意整数均可唯一分解成若干质数幂次之积的形式：$x=p_1^{a_1}p_2^{a_2}…p_n^{a_n}$，其中 $p_i$ 表示从 $2$ 开始第 $i$ 个质数。
质数检测：
即判断一个数是否是质数。
暴力：
求出 $[1,n]$ 内的所有整除 $n$ 的数。
时间复杂度：$O(n)$。
根号均衡：
$a\times b=n,\min\lbrace a,b\rbrace\leq \sqrt n$。
对于一个数的约数，它们是成对出现的。确定了其中之一，那么另一个也就确定了。
而根据上述不等式，启发我们，如果只枚举 $\min\lbrace a,b\rbrace$，那么只需要枚举到 $\sqrt n$ 即可。
时间复杂度：$O(\sqrt n)$。
质数优化：
引理：若 $a\mid b,b\mid c$，则 $a\mid c$。
同时，质数是不存在大于 $1$ 的真因子的，所以可以只判断 $[1,\sqrt n]$ 的质数是否是 $n$ 的约数即可。
或者根据唯一分解定理，也可以得知只要判断质因子即可。
根据质数密度，可得时间复杂度：$O(\dfrac{\sqrt n}{\log\sqrt n})$，一般可直接写作 $O(\dfrac{\sqrt n}{\log n})$。
Miller-Rabin：
根据费马小定理，若 $p$ 是质数，则 $a^{p-1}\equiv 1\pmod p$，所以如果要检测 $p$ 是不是质数，可以尝试判断 $a^{p-1} \bmod p$ 的结果是否为 $1$。若不为 $1$ 则 $p$ 一定不是质数，但是反之不然。
所以仅仅判断 $a^{p-1}\bmod p$ 的结果是不够的。
注意到，若 $a^{\frac{p-1}{2}}\bmod p$ 的结果不是 $1$ 或 $p-1$，而 $a^{p-1}\bmod p$ 的结果是 $1$，那么 $p$ 一定不是质数。所以不断对指数除以 $2$ 判断即可。
同时，$\dfrac{p-1}{2}$ 可能就已经不是偶数了，所以一个底数可能还是不够，因此可以多选几个底数。一般选前 $9$ 个质数即可，或者随机生成几个数也行。
由上可以发现，这是一个随机化算法，其正确性和哈希冲突类似，同样是生日悖论模型，只要出现一次不是 $1$ 或 $p-1$，即可认为不是质数，在多次检测过后还是错误的概率会非常小。
一个小细节是因为指数按 $2$ 倍递增，所以可以每次按 $2$ 倍增，总的时间复杂度为 $O(c\log n)$，其中 $c$ 为选择用于检测的底数个数。
分解质因数：
即求出一个数的所有质因数（一般认为也需要求出对应指数）。
暴力分解：
此处暴力分解指根号均衡时的暴力分解，根号均衡质数检测时，若某质数是 $x$ 的因子，则不断将 $x$ 除以此质数，因为根据唯一分解定理，将某质因子从 $x$ 中除去后，并不影响后续别的质因子的分解。
时间复杂度：$O(\dfrac{\sqrt n}{\log n})$。
若在分解除以质因子的同时判断当前枚举的质数$\leq \sqrt x$，则对于实际运行中的平均效率而言，普遍跑不满这个 $O(\dfrac{\sqrt n}{\log n})$。当然，最坏情况还是会跑满的（即：$x=p_i^2$ 时）。
枚举倍数：
若枚举 $i$，同时枚举 $i$ 的倍数，将 $i$ 作为因子放到 $i$ 的倍数的因子集合中。则可以处理出 $[1,n]$ 所有数的所有约数。时间复杂度：$O(n\log n)$。
因为调和级数：$\dfrac11+\dfrac12+…+\dfrac1n\approx\ln n$。
若仅仅需要质因子，也容易，因为质数的约数只有 $1$ 和它本身，所以当从小到大枚举到 $i$ 时，$i$ 对于的约数集合只有 $1$，那么它就是质数。
（所以，使用此方法也可以筛质数。或者说，这本质上和埃氏筛的基本思想是一致的）
Pollard-rho：
Pollard-rho 同样是一种随机化算法。
考虑一个数列：$x_n=(x_{n-1}^2+c)\bmod p$，期望经过多少项后会有两项值相等。
同样是“生日悖论”模型，大约 $O(\sqrt p)$ 项后会出现相同的两项。
引理：若 $p=p_1\times p_2$，则 $x_n=(x_{n-1}^2+c)\bmod p$ 的循环节是 $x_n=(x_{n-1}^2+c)\bmod p_1$ 和 $x_n=(x_{n-1}^2+c)\bmod p_2$ 的倍数。
根据引理可得，$p$ 对于数列的循环节一定是 $p_1,p_2$ 的循环节。
但是无法确定，所以第 $n$ 项和前 $[1,n-1]$ 项都做差，那么其中一定会有一个 $p_1$ 或 $p_2$ 的循环节。根据前文内容，可得这个 $n$ 是期望 $O(\sqrt{p_1}),O(\sqrt{p_2})$ 的。
引理：$\gcd(a,b)\mid b$。
求 $\gcd(a,b)$，是容易的，通过辗转相除法可以 $O(\log n)$ 求得，所以若 $\gcd(a,b)\neq 1\land\gcd(a,b)\neq b$，则我们就得到了 $b$ 的一个非平凡因子。
（所以也就是说，最理想状态下，随机一个数，然后用它和 $n$ 求 $\gcd$ 就得到了 n 的一个因子，然后不断递归，可以 $O(\log n)$ 分解质因数。同时，一个数的质因数规模最大就是 $O(\log n)$ 的，所以分解质因数的理论时间复杂度不应该比 $O(\log n)$ 还快）
所以，判断 $n$ 是否是循环节的方式就是作差后求 $\gcd$ 然后判断是否是 $1$。
综上：即可在单次期望 $O(\sqrt p_1\log p)$ 的时间复杂度内得到 $p$ 的一个因数（算上求 $\gcd$ 的时间复杂度）。
引理：$\exist\ i\in[1,m],\gcd(a_i,n)\neq 1$，则 $\gcd(a_1\times a_2\times…\times a_m,n)\neq 1$。
引理：$p=p_1\times p_2$，若 $p_1\mid a$，那么满足 $a\mid b$ 的 $b$ 对 $p$ 取模后的结果还是 $p_1$ 的倍数。
根据引理，结合 Pollard-rho 期望的是找到那个不等于 $1$ 的 $\gcd$，所以可以将 $\log n$ 次差的结果乘起来作 $\gcd$，这样均摊后的时间复杂度就能做到 $O(\sqrt p)$。
而根据前文的根号均衡 $\min\lbrace p_1,p_2\rbrace\leq \sqrt p$，所以一般认为 Pollard-rho 的时间复杂度为 $O(\sqrt{\sqrt n})=O(n^{\frac14})$。
而要完全质因数分解一个数，则需要分解 $O(\log n)$ 次因子。
（上述时间复杂度模型相当于每次划分指数集合，每次划分后的集合大小都会变小，划分到 $1$ 为止，最后的划分次数就是初始集合大小，而质因数分解后的指数大小为 $O(\log n)$，那么即分解 $O(\log n)$ 次因子）
综上：Pollard-rho 分解质因数的总时间复杂度为：$O(n^{\frac14}\log n)$。
tips：
实际上，Pollard-rho 分解到质数后，不存在非平凡因子了，时间复杂度就失效了，所以还要特判当前递归状态是否是质数。（根据质数检测的时间复杂度不同，时间复杂度不同，但是由于质因子只有 $O(\log n)$，所以只要进行 $O(\log n)$ 次质数检测，使用 Miller-Rabin 的话不会影响时间复杂度瓶颈）
筛质数：
筛质数是指预处理 $[1,n]$ 的所有质数。
埃氏筛：
基本思想是一个大于 $1$ 的整数的不为自身的倍数不会是质数。
所以从小到大枚举 $i$，然后标记它的所有倍数即可。若枚举到 $i$ 的时候，$i$ 没有被标记过，则 $i$ 是一个质数。
根据调和级数，时间复杂度：$O(n\log n)$。
埃氏筛优化：
根据根号均衡的思路，枚举倍数时，另一个乘数，可以从 $i$ 开始枚举，而不是 $2$。
通过此优化，时间复杂度优化至：$O(n\log\log n)$。
欧拉筛（线性筛）：
基本思想同样是标记每一个非质数，但是用 $x$ 最小的质因数标记它。保证了每个数最多被标记一次，所以时间复杂度为 $O(n)$。$O(n)$ 时间复杂度即线性，所以欧拉筛也通常被称为线性筛。
具体流程，仍然从小到大枚举 $i$，然后枚举 $[1,i]$ 处理好的质数，标记 $i\times p_j$，若 $i\equiv 0\pmod {p_j}$，则停止标记过程，继续枚举 $i$。当枚举到的 $i$ 未被标记时，$i$ 就是质数。
其它筛：
还有许多其它的筛法。但是算法竞赛中以上两种筛法足以应付几乎所有情况了。
因为质数密度为 $O(\dfrac{n}{\log n})$ 的，所以任何筛法的时间复杂度都不会低于这个阈值。
扩展：
欧拉筛也常用作预处理积性函数。事实上 $prime(i)=\begin{cases}1& i\ is\
a\ prime\0&else\end{cases}$ 也是一个积性函数。
addition：
由于质数筛的标记数组只存在 $0/1$，所以若使用 bitset 存储，其效率会得到不小的提升。相较 bool 数组，空间也能得到优化。