数论——质数

定义

质数，是一个只能被 111 和它自身整除的自然数，且大于 111 。简单来说，质数是一个大于 111 的整数，除了 111 和它自己以外，不能被其他任何数整除。

分布

NNN 以内质数个数：

F(N)≈Nln⁡N

F(N)\approx \frac{N}{\ln N}

F(N)≈lnNN​

即每 ln⁡N\ln NlnN 个数中就有可能出现一个质数。

所以在 x≤1014x\le10^{14}x≤1014 时，暴力寻找比 xxx 大（小）的第一个质数时可在一秒内查询到

判定

试除法

不难发现一个数的因子是成对出现的，即若 d1 ∣ x (d1≥x)d_1\ |\ x\ (d_1\ge\sqrt x)d1​ ∣ x (d1​≥x​) ，则有 d2=xd1≤xd_2 = \large{\frac{x}{d_1}}\le\sqrt xd2​=d1​x​≤x​

所以我们只需要扫描 2∼N2\sim \sqrt N2∼N​ 的所有整数 xxx ，若 ∀ x ∤N\forall\ x\ \nmid N∀ x ∤N 则 NNN 是质数，否则 NNN 是合数

代码

bool is_prime(int n) {

if (n < 2) return false;

for (int i = 2; i * i <= n; i++)

if (!(n % i))

return false;

return true;

}

筛法

Eratosthenes\text{Eratosthenes}Eratosthenes 筛法

Eratosthenes\text{Eratosthenes}Eratosthenes 筛法通过反复标记合数（非质数）来筛选出质数。这个算法的时间复杂度为 O(nlog⁡log⁡n)\mathcal{O}(n \log \log n)O(nloglogn) 。

在 n≤107n\le 10^7n≤107 埃氏筛时间复杂度在 O(4×107)\mathcal{O}(4\times10^7)O(4×107) 左右，埃氏筛可以处理，但是常数过大时可能 TLE

代码

void primes(int n) {

memset(v, 0, sizeof(v)); // 合数标记

for (int i = 2; i <= n; i++) {

if (v[i]) continue;

cout << i << '\n'; // i 是质数

for (int j = 1; j <= n / i; j++) v[i * j] = 1;

}

}

Euler\text{Euler}Euler 筛法（欧拉筛法或线性筛法）

不难发现 Eratosthenes\text{Eratosthenes}Eratosthenes 筛法仍然会重复标记合数，例如 121212 会被 222 与 333 标记，在标记 222 的倍数时， 12=2×612 = 2 \times 612=2×6 ，在标记 333 的倍数时， 12=3×412 = 3 \times 412=3×4 。本质是因为我们无法用确定的方式标记 121212 ，所以我们尝试只用每个数的最小质因子标记，即让 121212 只被 222 标记。

线性筛法通过“从小到大累积质因子”的方式标记合数。设数组 vvv 记录每个数的最小质因子，我们通过以下方式维护 vvv 。

依次考虑 2∼N2\sim N2∼N 之间的每一个数 iii 。若 vi=0v_i = 0vi​=0 ，说明 iii 是质数，把它记录下来。扫描不大于 viv_ivi​ 的每个质数 ppp ，令 vi×p=pv_{i\times p} = pvi×p​=p 。

算法的关键在于步骤 333 中的不大于，这样可使任意的 iii 只被它的最小质因子标记，可以尝试用反证法证明。

证明：

假设当前枚举到 iii ， iii 的最小质因子为 viv_ivi​ ， j>vij > v_ij>vi​ 。

当我们尝试标记 i×ji \times ji×j 时， i×j=vi×ivii \times j = v_i \times \large\frac{i}{v_i}i×j=vi​×vi​i​ ，此时就不满足被 i×ji\times ji×j 的最小质因子标记。

证毕

代码

for (int i = 2; i <= n; i++) {

if (!v[i]) v[i] = i, primes.push_back(i); // i 是质数

// 给当前的数 i 乘上一个最小质因子

for (int p : primes) {

// i 有比 p 更小的质因子，或者超出 n 的范围 停止循环

if (p > v[i] || p * i > n) break;

// p 是合数 i * p 的最小质因子

v[i * p] = p;

}

}

质因数分解

算数基本定理

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

N=p1c1×p2c2×⋯×pmcm=∏i=1mpici

N = p_1^{c_1}\times p_2^{c_2}\times \cdots \times p_m^{c_m} = \prod_{i=1}^{m}p_i^{c_i}

N=p1c1​​×p2c2​​×⋯×pmcm​​=i=1∏m​pici​​

其中：ci∈N+c_i \in \mathbb{N}_+ci​∈N+​ ， pip_ipi​ 都是质数，并且满足 p1

由此可得： NNN 至多只有一个大于 N\sqrt NN​ 的质因子，考虑反证法。

证明：

设 pi, pjp_i,\ p_jpi​, pj​ 分别为 NNN 的两个不同的质因子且 pi>N, pj>Np_i>\sqrt N,\ p_j>\sqrt Npi​>N​, pj​>N​ 。

所以 pi×pj>Np_i\times p_j > Npi​×pj​>N ， 与 pici×pjcj≤Np_i^{c_i}\times p_j^{c_j}\le Npici​​×pjcj​​≤N 矛盾。

证毕

试除法

试除法 是一种用于分解正整数为质因数乘积的基本方法。基本思路是：

从最小的质数开始 ，逐一尝试除以待分解的整数。如果当前质数能整除该整数，则记录下该质数，并将整数除以该质数。重复上述过程，直到待分解的整数为 1。

不难发现，进行以上算法步骤需要从 2∼n−12\sim n - 12∼n−1 进行试除，效率较低。

已知大于 n\sqrt nn​ 的质因子至多只有一个，所以可通过下面的方式优化:

只检查到 n\sqrt nn​

代码

void divide(int n) {

m = 0;

for (int i = 2; i * i <= n; i++)

if (!(n % i)) { // i 是质数

p[++m] = i, c[m] = 0;

while (!(n % i)) n /= i, c[m]++;

}

if (n > 1) // n 是质数

p[++m] = n, c[m] = 1;

for (int i = 1; i <= m; i++) cout << p[i] << '^' << c[i] << '\n';

}