0x31 质数

定义

若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该正整数为合数。

在整个自然数集合中, 质数的数量不多, 分布比较稀疏, 对于一个足够大的整数 $N$ , 不超过 $N$ 的质数大约有 $N / \ln N$ 个, 即每 $\ln N$ 个数中大约有 1 个质数。

$\spadesuit$ 质数的判定

试除法

若一个正整数 $N$ 为合数，则存在一个能整除 $N$ 的数 $T$ ，其中 $2 \leq T \leq \sqrt{N}$ 。证明：

由定义得，因为 $N$ 是合数，所以存在一个能整除 $N$ 的数 $M$ ，其中 $2 \leq M \leq N - 1$ 。

反证法。假设命题不成立，那么这样的数 $M$ 一定满足 $\sqrt{N} +1\leq M\leq N - 1$

因为 $M$ 能整除 $N$ , 所以它们的商 $N / M$ 也能整除 $N$ . 而 $2 \leq N / M \leq \sqrt{N}$ , 令 $T = N / M$ , 这与假设矛盾。故假设不成立, 原命题成立。

证毕。

根据上述命题，我们只需要扫描 $2\sim \sqrt{N}$ 之间的所有整数，依次检查它们能否整除 $N$ ，若都不能整除，则 $N$ 是质数，否则 $N$ 是合数。试除法的时间复杂度为 $O(\sqrt{N})$ 。

bool is_prime(int n) { for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; }

“试除法”作为最简单也最经典的确定性算法，是我们在算法竞赛中通常会使用的方法。有一些效率更高的随机性算法，例如“Miller-Robbin”等，有较小的概率把合数错误判定为质数，但多次判定合起来的错误概率趋近于零，感兴趣的读者可以自行查阅并学习。

$\spadesuit$ 质数的筛选

给定一个整数 $N$ ，求出 $1\sim N$ 之间的所有质数，称为质数的筛选问题。

Eratosthenes 筛法

Eratosthenes 筛法基于这样的想法: 任意整数 $x$ 的倍数 $2x, 3x, \cdots$ 都不是质数。根据质数的定义, 上述命题显然成立。

我们可以从2开始，由小到大扫描每个数 $x$ ，把它的倍数 $2x, 3x, \dots, [N / x] * x$ 标记为合数。当扫描到一个数时，若它尚未被标记，则它不能被 $2 \sim x - 1$ 之间的任何数整除，该数就是质数。

Eratosthenes 筛法的进行过程如下：

3,45,67,89,1011，12…   
45,67,89,1011，12  
4767,89,1011，12  
47689,1011，12  
4689,1011，12  
4689,1011，12

另外，我们可以发现，2和3都会把6标记为合数。实际上，小于 $x^{2}$ 的 $x$ 的倍数在扫描更小的数时就已经被标记过了。因此，我们可以对Eratosthenes筛法进行优

化，对于每个数 $x$ ，我们只需要从 $x^{2}$ 开始，把 $x^{2}, (x + 1)*x,\dots ,[N / x]*x$ 标记为合数即可。

void primes(int n) {  
    memset(v, 0, sizeof(v)); // 合数标记  
    for (int i = 2; i <= n; i++) {  
        if (v[i]) continue;  
        cout << i << endl; // i是质数  
        for (int j = i; j <= n/i; j++) v[i*j] = 1;  
    }  
}

Eratosthenes 筛法的时间复杂度为 $O\left(\sum_{\text{质数} p \leq N} \frac{N}{p}\right) = O(N \log \log N)$ 。该算法实现简单，效率已经非常接近于线性，是算法竞赛中最常用的质数筛法。

线性筛法

即使在优化后（从 $x^{2}$ 开始），Eratosthenes 筛法仍然会重复标记合数。例如 12 既会被 2 又会被 3 标记，在标记 2 的倍数时， $12 = 6 * 2$ ，在标记 3 的倍数时， $12 = 4 * 3$ 。其根本原因是我们没有确定出唯一的产生 12 的方式。

按照这个思想，我们在生成一个需要标记的合数时，每次只向现有的数中乘上一个质因子，并且让它是这个合数的最本质因子。这相当于让合数的质因子从大到小累积，即让12只有 $3*2*2$ 一种产生方式。具体地说，我们采用如下的线性筛法，其中 $\pmb{v}$ 数组记录每个数的最小质因子。每个合数只会被它的最本质因子筛一次，时间复杂度为 $O(N)$

int v[MAX_N], prime[MAX_N];  
void primes(int n) {  
    memset(v, 0, sizeof(v)); // 最小质因子  
    m = 0; // 质数数量  
    for (int i = 2; i <= n; i++) {  
        if (v[i] == 0) { // i是质数  
            v[i] = i;  
            prime[++m] = i;  
        }  
    // 给当前的数i乘上一个质因子  
    for (int j = 1; j <= m; j++) {  
        // i有比prime[j]更小的质因子，或者超出n的范围  
        if (prime[j] > v[i] || prime[j] > n/i) break;  
    }  
}

//prime[j]是合数i\*prime[j]的最小质因子v[i\*prime[j]]  $=$  prime[j];1}for(int  $\mathrm{i} = 1$  ;i  $\text{一} = \text{m}$  ;i++)cout<<prime[i]<<endl;

$\spadesuit$ 质因数分解

算术基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：

N = p _ {1} ^ {c _ {1}} p _ {2} ^ {c _ {2}} \dots p _ {m} ^ {c _ {m}}

其中 $c_{i}$ 都是正整数， $p_{i}$ 都是质数，且满足 $p_{1} < p_{2} < \dots < p_{m}$ 。

试除法

结合质数判定的“试除法”和质数筛选的“Eratosthenes 筛法”，我们可以扫描 $2 \sim \left\lfloor \sqrt{N} \right\rfloor$ 的每个数 $d$ ，若 $d$ 能整除 $N$ ，则从 $N$ 中除掉所有的因子 $d$ ，同时累计除去的 $d$ 的个数。

因为一个合数的因子一定在扫描到这个合数之前就从 $N$ 中被除掉了，所以在上述过程中能整除 $N$ 的一定是质数。最终就得到了质因数分解的结果，易知时间复杂度为 $O(\sqrt{N})$ 。

特别地，若 $N$ 没有被任何 $2\sim \sqrt{N}$ 的数整除，则 $N$ 是质数，无需分解。

void divide(int n) {  
    m = 0;  
    for (int i = 2; i <= sqrt(n); i++) {  
        if (n % i == 0) { // i是质数  
            p[++m] = i, c[m] = 0;  
        while (n % i == 0) n /= i, c[m]++; //除掉所有的i}  
    }  
    if (n > 1) // n是质数  
        p[++m] = n, c[m] = 1;  
    for (int i = 1; i <= m; i++)  
        cout << p[i] << '^' << c[i] << endl;  
}

“Pollard's Rho”算法是一个比“试除法”效率更高的质因数分解算法，不过这超出了我们的探讨范围，感兴趣的读者可以自行查阅并学习。

【例题】Prime Distance FOJ2689

给定两个整数 $L, R$ （ $1 \leq L \leq R \leq 2^{31}, R - L \leq 10^6$ ），求闭区间 $[L, R]$ 中相邻两个质数的差最大是多少，输出这两个质数。

$L, R$ 的范围很大，任何已知算法都无法在规定时间内生成 $[1, R]$ 中的所有质数。但是 $R - L$ 的值很小，并且任何一个合数 $n$ 必定包含一个不超过 $\sqrt{n}$ 的质因子。

所以，我们只需要用筛法求出 $2\sim \sqrt{R}$ 之间的所有质数。对于每个质数 $p$ ，把 $[L,R]$ 中能被 $p$ 整除的数标记，即标记 $i * p\left(\left[\frac{L}{p}\right] \leq i \leq \left[\frac{R}{p}\right]\right)$ 为合数。

最终所有未被标记的数就是 $[L, R]$ 中的质数。对相邻的质数两两比较，找出差最大的即可。

时间复杂度为 $O\left(\sum_{\text{质数} p \leq \sqrt{R}} \frac{R - L}{p}\right) = O\left(\sqrt{R} \log \log \sqrt{R} + (R - L) \log \log R\right)$ 。

【例题】阶乘分解

给定整数 $N(1 \leq N \leq 10^6)$ ，试把阶乘 $N!$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_i$ 和 $c_i$ 即可。

若把 $1 \sim N$ 每个数分别分解质因数，再把结果合并，时间复杂度过高，为 $O(N \sqrt{N})$ 。显然， $N!$ 的每个质因子都不会超过 $N$ ，我们可以先筛选出 $1 \sim N$ 的每个质数 $p$ ，然后考虑阶乘 $N!$ 中一共包含多少个质因子 $p$ 。

$N!$ 中质因子 $p$ 的个数就等于 $1 \sim N$ 每个数包含质因子 $p$ 的个数之和。在 $1 \sim N$ 中， $p$ 的倍数，即至少包含 1 个质因子 $p$ 的显然有 $\lfloor N / p \rfloor$ 个。而 $p^2$ 的倍数，即至少包含 2 个质因子 $p$ 的有 $\lfloor N / p^2 \rfloor$ 个。不过其中的 1 个质因子已经在 $\lfloor N / p \rfloor$ 里统计过，所以只需要再统计第 2 个质因子，即累加上 $\lfloor N / p^2 \rfloor$ ，而不是 $2 * \lfloor N / p^2 \rfloor$ 。

综上所述， $N!$ 中质因子 $\pmb{p}$ 的个数为：

\left\lfloor \frac {N}{p} \right\rfloor + \left\lfloor \frac {N}{p ^ {2}} \right\rfloor + \left\lfloor \frac {N}{p ^ {3}} \right\rfloor + \dots + \left\lfloor \frac {N}{p ^ {\lfloor \log_ {p} N \rfloor}} \right\rfloor = \sum_ {p ^ {k} \leq N} \left\lfloor \frac {N}{p ^ {k}} \right\rfloor

对于每个 $p$ ，只需要 $O(\log N)$ 的时间计算上述和式。故对整个 $N!$ 分解质因数的时间复杂度为 $O(N\log N)$ 。

0x31_质数