质数浅谈

· · 个人记录

这篇博文讲的只是质数入门级的东西．

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<k\le\lfloor \frac{N}{x} \rfloor \} 标记为合数．经过上述步骤，当扫描到一个尚未标记的数 x，必定满足不可被 [2,\,x-1] 中任一整数整除，该数即为质数．

如果还不能理解，就摆出这幅著名的动图．

参照上图，在标记的过程中，\{kx\mid\,k\in\mathbb{N^* },\,1<k<x\} 已经在扫描更小的数时被标记（6 在扫描 3 时被标记之前已经在扫描 2 时被标记）．据此对 Eratosthenes 筛选法作出优化，即对于扫描到的每个 x，将 \{kx\, \mid\,k\in\mathbb{N^* },\,x\le k\le\lfloor \frac{N}{x} \rfloor \} 标记为合数即可．

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 <N}\frac{N}{p}\mid p\in\mathbb{P}) \approx \Theta(N\log\log N)（不要问我这个等号怎么推出来的，我也不知道），实现简单且效率接近线性，是很常用的质数筛法．

线性筛法

似乎也被称为欧拉筛吧，这个名字有什么依据我就不知道了．

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<p_2<\cdots<p_m)

其中，\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