质数
质数的定义ψ(｀∇´)ψ
简单来说就是除了 \(1\) 和它本身以外没有任何因数。
本文记 \(\text{PRIME}(n)\) 表示 \(n\) 为质数。
有两个重要结论：
- 结论 1：对于足够大的 \(n \in \mathbb{N}^*\)，\([1,n]\) 中的素数个数约为 \(\frac{n}{\ln n}\) 个 （对数结论）
- 结论 2：若 \(\lnot \text{PRIME}(n)\)，则 \(\exists T \in [2,\sqrt{n}]\)，使得 \(T|n\)。（根号结论）
此处记 \(\sqrt{n} = \lfloor\sqrt{n}\rfloor\)。
判断是否为质数ψ(｀∇´)ψ
由根号结论可以得到一个比较显然的质数判断算法：
令 \(x\in[2,\sqrt{n}]\)，判断是否存在 \(x | n\)。若存在 \(\Rightarrow \lnot \text{PRIME}(n)\)。
复杂度 \(O(\sqrt{n})\)。
1 2 3 4 5 6 | |
质数筛法ψ(｀∇´)ψ
泛化：用来求 \([1,n]\) 中的素数集合。
埃氏筛ψ(｀∇´)ψ
基于一个显然的结论：\(\forall x \in \mathbb{N}^*\)，\(\lnot \text{PRIME}(kx),(k = 2, 3, 4,\dots)\)
一个 simple 的想法：枚举 \(2 \to n\)，如果 \(i\) 没有被标记为合数，则 \(\text{PRIME}(i)\)，然后标记所有的 \(ki\)。如果 \(i\) 已经被标记，那么标记所有的 \(ki\)，初始的时候 \(2\) 没有被标记。复杂度 \(O(n\times\sum\frac{n}{i})=O(n^2)\)。
发现这个做法会重复标记一个数很多次，比如 \(12\) 就会被 \(2, 3, 4, 6\) 都标记一次。
那么考虑一个简单的优化：显然对于 \(\forall rx,r\in[2,x)\)，\(rx\) 必然会在被 \(x\) 标记到的时候提前被标记到。因为 \(r\) 肯定比 \(x\) 小，那么 \(r\) 肯定就标记过了 \(rx\)，所以我们可以直接从 \(k = x\) 开始标记 \(kx\)。
复杂度 \(O(\sum\limits_{r\le n \land \text{PRIME}(r)}\dfrac{n}{r}) = O(n \log \log n)\)。
1 2 3 4 5 6 7 8 9 10 11 | |
线性筛ψ(｀∇´)ψ
又叫欧拉筛。
考虑到埃氏筛还是会重复标记很多数。
还是举一个例子：\(12 = 2 \times 6 = 3 \times 4\)，这个例子下，\(12\) 会被 \(2,3\) 各筛一次。
问题所在就是，一个数并不能唯一确定一个数来标记它。
思索一下，可以使用一个数的最小质因子来标记它，因为质因子不会再拆分成别的因数，使用最小的质因子是因为确定起来方便。
记 \(mp(n)\) 表示 \(n\) 的最小质因子，显然，如果 \(\text{PRIME}(i) \Rightarrow mp(i) = i\)。
那么当扫到某一个数 \(i\) 且 \(i\) 没有被标记的时候，令 \(mp(i) = i\) ，记录质数 \(i\)。然后对于 \(i\) （不管它是不是质数）枚举所有比 \(mp(i)\) 小或者等于 \(mp(i)\) 的质数 \(j\)（从已经确定的质数集合里面选），标记 \(i\times j\) 为合数，并令 \(mp(i\times j) = j\)。
换一种说法，就是从大到小累积质因子，这样能唯一确定每个数的组成方式，比如 \(12\) 就是 \(3 \times 2 \times 2\)。
筛出 \(12\) 的过程是；先扫描到 \(2\)，此时合法的 \(j\) 只能是 \(2\)，所以标记 \(4\) 为合数，然后令 \(mp(4)=2\)，扫描到 \(3\)，发现 \(2,3\) 可以充当 \(j\)，所以标记 \(6,9\)，\(mp(6) = 2,mp(9) = 3\)。扫到 \(4\) 的时候，发现只有 \(2\) 可以充当 \(j\)，于是标记 \(8\)， \(mp(8)=2\)，当扫描到 \(6\) 的时候，就标记了 \(12\)，并令 \(mp(12) = 2\)。
因为每个合数 \(i \times j\) 只会被他的最小质因子 \(j\) 筛一次，所以复杂度是 \(O(n)\) 的。
这样还顺便求了每个数的最小质因子。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
质因数分解ψ(｀∇´)ψ
泛化：分解一个数的所有质因子
- 算术基本定理：任何一个大于 \(1\) 的正整数都可以唯一分解为有限个质数的乘积。
也叫唯一分解定理，可以写成 \(N = p_1^{c1}\times p_2^{c2}\times p_3^{c3}\times \dots p_m^{cm}, c_i \in \mathbb{N}^*, p_i < p_{i + 1},\text{PRIME}(p_i)\)。
证明
良序原理的应用
良序原理：非负整数集当中的每个非空子集都有一个最小元素。
这个是一个公理，不用证明，但是它的应用很强大：
对任意非负整数 \(n\)，我们现在想要证明命题 \(\forall n \in \mathbb{N}, P(n)\) 成立，有如下的一套模板：
- 定义 \(C\) 为 \(P\) 的反例集合，即 \(C = \{n \in \mathbb{N} | P(n) = \text{false}\}\)。
- 找到 \(\min\{n\} \in C\)，尝试说明能推理出一个比 \(n\) 更小的元素 \(e \in C\)，推出矛盾，证明 \(C\) 为空集。
- 进而证明原命题为真。
引理
若 \(p\) 为质数且 \(p | ab\)，则 \(p | a \text{ or } p | b\)。
证明不能考虑约数集合，不然就成了一个循环论证。
所以我们换个思路，能不能用线性组合相关的知识来证明呢（因为这里有整除的嘛）
首先如果 \(\gcd(a, p) = p\)，这个一定成立，\(b\) 同理。
然后考虑 \(\gcd(a, p) \not= p\)，会是怎么样的，。
因为 \(p\) 为质数，所以 \(\gcd(a, p) = 1\)，也就是说我们在考虑证 \(p | b\)。
因为 \(\gcd(a, p)\) 为 \(a, p\) 的线性组合，根据 Bezout 定理存在 \(u,v \text{ s.t. } ua+vp=1\)。
那么两边乘上一个 \(b \Rightarrow b = u(ab) + (vb)p\)。
也就是，\(b\) 是 \(ab, p\) 的线性组合，因为 \(p | ab, p | p\)，所以 \(p | b\)。
Q.E.D.
推论：若 \(p\) 为质数，且 \(p | \prod\limits_{i = 1}^{n}a_i\)，则 \(p\) 能整除某些 \(a_i\)。
我们可以考虑应用良序原理的思路。
我们假设 \(\exists n \in C\)，也就是说 \(n\) 可以写成两个不同的质数序列的乘积。
令 \(n = p_1\times p_2 \dots p_s = q_1 \times q_2 \dots q_t\)。
其中 \(p, q\) 均为单调不增的序列，我们钦定 \(p_1 \le q_1\)。
首先说明 \(p_1 = q_1\) 的情况，可以发现在这种情况下 \(\dfrac{n}{p_1}\) 也可以被写作两个不同的质数序列的乘积，因为 \(\dfrac{n}{p_1} < n\)，这和 \(n\) 最小矛盾，所以 \(p_1 < q_1\)。
那么，可以得到 \(\forall i \in[1,s], q_1 > p_i\)。
然而，\(q_1 | n = \prod\limits_{i = 1}^{s} p_i\)，根据引理，这说明 \(p_1\) 可以整除某些 \(p_i\)，即 \(\exists i, q_1 < p_i\)，矛盾。
Q.E.D.
- 试除法：
考虑一个埃氏筛的变式，结合根号结论。
想法：扫一遍 \(d\in[2,\sqrt{n}]\)，若 \(d|n\)，不断的除掉 \(n\) 中的 \(d\)，记录 \(c\) 即可。
因为从小到大，所以每次能整除 \(n\) 的 \(d\) 必然是质数，是合数的之前都除掉了。
复杂度 \(O(n)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 | |