质数浅谈
Yu36c343
·
2019-08-10 22:52:06
·
个人记录
这篇博文讲的只是质数入门级的东西．
OI数论的开始，就是素数．
素数的一些性质成为OI出题的热点，于是我们不得不学习令人心烦的数论．
定义
众所周知
若一个正整数无法被除了 1 和它自身之外的任何自然数整除，则称该数为质数（prime number，又称素数），否则称该数为合数（composite number）．
特别的，1 既不是质数，也不是合数．
由定义，2 是最小的质数，也是唯一的偶质数．
为了方便描述，在本文中，有时会用 \mathbb{P} 指代质数集合．
一、质数相关定理
然而并没有什么用QwQ．
质数无穷定理
我也不知道它叫什么，随便起了个名字qwq．
质数的个数是无限的．
读者自证不难．可以参考《几何原本》中的证明．
质数分布定理
预警：这一方面笔者不能写出很严谨的说明
在自然数集合中，质数分布较为稀疏．
对正实数 x，定义 \pi(x) 为不大于 x 的质数的个数，有：
\pi(x)\approx \frac{x}{\ln x}
推论1 ：从不大于 n 的自然数随机选一个，它是素数的概率约为 \frac{1}{\ln n}．
推论2 ：第 n 个质数的渐进估计为 n \ln n．
二、质数的判定
问题
给定一个大于 1 的正整数 N，判定其是否为质数．
试除法 及其常数优化
引理一
若一个正整数 N 为合数，则 [2,\,\sqrt{N}] 中存在整数 i，使得 i\mid N．
证明： 显然
由合数定义，必定存在正整数 j 满足 j\mid N,\,j\in [2,\,N-1]；
假设原命题不成立，则 j\in[\sqrt{N}+1,\,N-1]；而由于 j\mid N，显然，它们的比 i=\frac{N}{j} 也满足 i\mid N，且 i\in[2,\,\sqrt{N}]；这与假设矛盾．故假设不成立，原命题成立．
证毕．
算法思想
由引理一，我们只需要扫描 [2,\,\sqrt{N}] 中的所有整数，依次检查它们能否整除 N，若都不能整除，则 N 为质数，否则 N 为合数．
C++ code
bool if_prime (int n) {
if (n == 1) return false;
for (int i = 2, i * i <= n; ++i)
if (!(n % i)) return false;
return true;
}
试除法的时间复杂度为 \Theta(\sqrt{N})，是最简单也是最常用的算法．
引理二
\forall p\in\complement_{\{2,3\}}\mathbb{P},\,p\in\{x\mid x=6k\pm1,\,k\in\mathbb{N_+}\}
证明：
显然，形如 6k、6k+2、6k+3、6k+4 （k\in\mathbb{N}）的自然数均能为 2 或 3 整除．
由此，除 2 和 3 本身外的所有质数，只可能为 6k\pm1\,(k\in\mathbb{N_+}) 的样式．
思想
由引理二，我们只需特判 2 和 3，在 [2,\,\sqrt{N}] 中枚举 6k\pm1 即可．
C++ code
bool if_prime (int n) {
if (n == 1) return false;
if (n == 2 || n == 3) return true;
if (n % 6 != 1 && n % 6 != 5) return false;
for (int i = 5, i * i <= n; i += 6)
if (!(n % i && n % (i + 2))) return false;
return true;
}
时间复杂度降至 \Theta(\frac{\sqrt{N}}{3})，可以防止被卡常（直接降 2/3）．
有一些效率更高的随机性算法（例如 Miller-Robbin），有较小的概率把合数判定为质数，但多次判定合起来的错误概率趋近于零，但超出了我们的讨论范围 （其实是我还没有熟练掌握），在此只捎带一提．
三、质数的筛选
问题：
给定正整数 N，求出 [1,\,N] 中的所有质数．
Eratosthenes 筛选法
出于显而易见的原因， 通常被称为埃氏筛．
Eratosthenes（BC276-BC194），希腊哲学家、 数学家，约 BC240 计算地球的直径误差小于 2\%，为当时世界最早最准确 （逐渐偏离主题）．
算法思想
由质数定义可知，任一整数 x 的倍数 \{2x,3x,\cdots\} 都不为质数．
我们从 2 开始，从小到大扫描每个数，将其倍数 \{kx\, \mid\,k\in\mathbb{N^* },\,1 如果还不能理解，就摆出这幅著名的动图． 参照上图，在标记的过程中，\{kx\mid\,k\in\mathbb{N^* },\,1 C++ code int m, p[M]; // m for number of primes bool vis[N]; void primes (int n) { // memset (vis, 0x00, sizeof vis), m = 0; vis[1] = true; for (int i = 2; i <= n; ++i) if (!vis[i]) { p[++m] = i; for (int j = i * i; j <= n; j += i) vis[j] = true; } } Eratosthenes 筛选法的时间复杂度为 \Theta(\sum_{p 线性筛法 似乎也被称为欧拉筛吧，这个名字有什么依据我就不知道了． Eratosthenes 筛选法 浪费的时间 标记一个数 x 为合数，仅当我们确定两个小于 x 的数的乘积（记为 i\cdot j）等于 x． 检查 Eratosthenes 筛选法，我们在标记 \{k\cdot x\, \mid\,k\in\mathbb{N^* },\,x\le k\le\lfloor \frac{N}{x} \rfloor \} 时，k 绝大多数情况下是已筛出的质数的倍数（例如 3\times 4，由于 4 是更小质数 2 的倍数，12 在扫描 3 时被标记之前已经在扫描 2 时被标记），此时的 k\cdot x 可以确定先前已被标记．在扫描更大的质数时，这种情况出现的频率大大增加，这就是 Eratosthenes 筛选法在 N 较大时浪费巨额时间的原因． 对于一个合数 x，在 i\cdot j 中 i 为最小质因子时第一次被标记．由此不难想到避免重复标记的方法，就是找到一个确定的 i\cdot j．不难想到，只要确定 i 是 x 的最小质因子即可（即 j 的最小质因子不小于 i）． 算法思想 筛出一个质数 i 后去枚举 j，这个枚举过程实现难度极大，因为要保证 j 的最小质因子不大于 i（如筛出 7 之后，要保证 2\nmid j、3\nmid j、5\nmid j），这种实现方式我们直接放弃． 相反，如果我们把 j 放到外层循坏，枚举小于其最小质因子的质数 p_i，这个过程不难实现：一旦枚举到的 p_i 成为 j 的因子，即说明 p_{i+1} 大于 j 的最小质因子（j 的最小质因子即 p_i），不会成为 p_{i+1}\cdot j 的最小质因子（p_{i+1}\cdot j 的最小质因子即 j 的最小质因子 p_i）．以此类推，一旦发现 p_i\mid j 时无需枚举 p_{i+1}，考虑下一个 j 即可． 如果仍感到理解困难，请读者参照下面的代码模拟一两次． C++ code int m, p[M]; bool vis[N]; void primes (int n) { // memset (vis, 0x00, sizeof vis), m = 0; vis[1] = true; for (int j = 2; j <= n; ++j) { if (!vis[j]) p[++m] = j; for (int i = 1; i <= m && p[i] * j <= n; ++i) { vis[p[i] * j] = true; if (!(j % p[i])) break; } } } 每个合数 p_i\times j 只会被它的最小值因子 p_i 筛一次，时间复杂度为 \Theta(N)． 四、质因数分解 算数基本定理 一称唯一分解定理 任一大于 1 的正整数 N 的正整数可被唯一分解为有限个质数的成绩，写作： N=\prod_{1\le i\le m}{p_i}^{c_i}\quad(c_i\in\mathbb{N^* },\,p_i\in\mathbb{P},\,p_1 其中，\prod_{i=1}^{m}{p_i}^{c_i} 称为 N 的标准分解式． 问题 给定一个大于 1 的正整数 N，求其标准分解式． 试除法 算法思想 结合 Eratosthenes 筛选法的思想，扫描 [2,\,\sqrt{N}] 的每个数 d，若 d\mid N，则除去 N 中的所有因子 d，同时累计除去 d 的个数． 因为一个合因子在扫描到这个合数之前必定已从 N 中除去，上述过程中得到的 d 一定为质数（问题所求的 p_i），除去 d 的次数即为 c_i． 特别地，若得不到 d，说明 N 本身即为质数，无需分解． 这样就得到了 N 的标准分解式． C++ code int m, p[M], c[M]; void divide (int n) { // m = 0; for (int i = 2; i * i <= n; ++i) if (!(n % i)) { p[++m] = i; while (!(n % i)) ++c[m]; } if (n > 1) p[++m] = n, ++c[m]; } 易知时间复杂度为 \Theta(\sqrt{N})． Pollard's Rho 是一个效率更高的算法，不过明显超出了我们的讨论范围 （然而其实是我不会），在此捎带一提． 小结 本文到此结束，但显然这只是很初步的内容，以后在学习的过程中会逐渐更新新的算法和新的理解，并加上一些代表性的例题． written by Yu-343