探索质数：从试除法到质数筛

引言

质数（Prime Number）是数学中的基本概念之一，指大于 1 且只能被 1 和自身整除的自然数。质数在密码学、计算机科学和数论中有着广泛的应用。本文将详细介绍质数的相关算法，包括试除法判断质数、分解质因数以及质数筛法（如埃拉托斯特尼筛法和线性筛法），并分析这些算法的原理和时间复杂度。

1. 试除法判断质数

ACWing 试除法判断质数

1.1 算法原理

试除法是最简单的判断质数的方法。对于一个数 $n$ ，如果它能被 2 到 $\sqrt{n}$ 之间的任意整数整除，则 $n$ 不是质数；否则， $n$ 是质数。

1.2 代码实现

bool isPrime(int n) {if (n <= 1) return false; // 1 不是质数for (int i = 2; i <= n/i; i++) {if (n % i == 0) return false; // 如果能整除，则不是质数}return true;
}

重要的事情说三遍：
tips:使用i<=n/i而不是i*i>=n的原因是担心i*i超出int范围导致错误
tips:使用i<=n/i而不是i*i>=n的原因是担心i*i超出int范围导致错误
tips:使用i<=n/i而不是i*i>=n的原因是担心i*i超出int范围导致错误

1.3 时间复杂度

最坏情况：每一次查询需要检查 2 到 $\sqrt{n}$ 的所有整数，假设有 $m$ 次查询，时间复杂度为 $O(m\sqrt{n})$ 。

2. 分解质因数

ACWing 分解质因数

2.1 算法原理

分解质因数是将一个合数分解为若干个质数的乘积。通过试除法，可以从最小的质数开始，逐步分解 $n$ 。具体步骤如下：

从最小的质数开始（通常是2），尝试将其除以给定的数。
如果能整除，则记录该质数，并继续对商进行同样的操作。
如果不能整除，则尝试下一个质数。
重复上述步骤直到剩下一个质数。

2.2 代码实现

void factorize(int n) {for (int i = 2; i <= n / i; i++) { // 循环从最小的质数2开始int cnt = 0; // 记录当前因子i出现的次数while (n % i == 0) { // 当前数能被i整除时cnt++; // 计数器加一n /= i; // 将n除以i}if(cnt){ // 如果计数器大于0，说明i是n的一个质因数cout << i << " " << cnt << endl; // 输出质因数和它的指数}}if (n > 1) { // 最后剩下的n如果是大于1的数，那它也是一个质因数cout << n; // 直接输出该质因数（因为它没有其他的质因数）}
}

2.3 实例演示

假设我们调用 factorize(12);，按照上述逻辑：

第一次循环： $i = 2$ ，12 能被 2 整除，因此进入 while 循环，cnt 增加到 2（因为 $12/2/2 = 3$ ），然后输出 2 2。
接下来， $n$ 变为 3，不再能被 2 整除，跳出第一个 for 循环。
检查剩余的 $n$ ) 是否大于 1，确实是，所以输出 3。

最终输出结果为：

2 2
3

这表示 12 可以被分解为 $2^2 \times 3$ 。

tips:这个算法之所以能够保证分解出来的因子都是质数，是利用while循环实现的。当把较小的质数完全分解出来后，这些质数的倍数也会一并排除。比如，当2被分离干净后，就不会再分解出偶数因子了。

2.3 时间复杂度

最坏情况：需要检查 2 到 $\sqrt{n}$ 的所有整数，在查询次数为 $m$ 的时候时间复杂度为 $O(m\sqrt{n})$ 。

3. 质数筛法

ACWing 筛质数

3.1 埃拉托斯特尼筛法（Sieve of Eratosthenes）

3.1.1 算法原理

埃拉托斯特尼筛法通过标记合数的方式筛选出质数。具体步骤如下：

初始化一个布尔数组 isPrime，标记所有数为质数。
从 2 开始，将每个质数的倍数标记为合数。
重复步骤 2，直到遍历完所有数。

这个过程像试除法的逆过程。试除法是把因子完全除调，这里是将倍数全部标记。

3.1.2 代码实现

void sieveOfEratosthenes(int n) {vector<bool> isPrime(n + 1, true);isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数for (int i = 2; i * i <= n; i++) {if (isPrime[i]) {for (int j = i * i; j <= n; j += i) {isPrime[j] = false; // 标记合数}}}// 输出质数for (int i = 2; i <= n; i++) {if (isPrime[i]) {cout << i << " ";}}
}

3.1.3 时间复杂度

时间复杂度： $\log \log n)$ 。
空间复杂度： $O (n)$ 。

3.2 线性筛法（欧拉筛法）

3.2.1 算法原理

线性筛法通过每个合数只被其最小质因数标记一次的方式，实现线性时间复杂度。具体步骤如下：

初始化一个布尔数组 isPrime，标记所有数为质数。
使用一个数组 primes 存储质数。
遍历每个数，如果是质数，则加入 primes 数组。
对于每个数，用 primes 数组中的质数标记合数。

3.2.2 代码实现

void linearSieve(int n) {vector<bool> isPrime(n + 1, true);vector<int> primes; // 存储质数for (int i = 2; i <= n; i++) {if (isPrime[i]) {primes.push_back(i); // i 是质数}for (int p : primes) {if (i * p > n) break;isPrime[i * p] = false; // 标记合数if (i % p == 0) break; // 保证每个合数只被标记一次}}// 输出质数for (int p : primes) {cout << p << " ";}
}

3.2.3 时间复杂度

时间复杂度： $O (n)$ 。
空间复杂度： $O (n)$ 。

4. 算法对比与应用场景

4.1 试除法

优点：实现简单，适用于单次判断质数。
缺点：时间复杂度较高，不适用于大规模数据。

4.2 分解质因数

优点：可以分解任意合数，适用于质因数分解问题。
缺点：时间复杂度较高，不适用于大规模数据。

4.3 埃拉托斯特尼筛法

优点：时间复杂度较低，适用于筛选一定范围内的质数。
缺点：空间复杂度较高，不适用于极大范围的质数筛选。

4.4 线性筛法

优点：时间复杂度最优，适用于大规模质数筛选。
缺点：实现稍复杂，空间复杂度较高。

5. 总结

通过本文的介绍，读者可以掌握质数相关算法的原理、实现方法以及应用场景。希望本文能够帮助读者深入理解质数及其相关算法。如果对质数或其他数论算法有更多疑问，欢迎在评论区留言讨论！