一、课上练习

编程练习

1. 素数判定：L3051
2. 埃式筛素数：L3052
3. 线性筛素数：L3053

二、知识总结

✨ 核心思想

对于大于 1 的自然数，素数和合数的定义如下：

• 素数（质数）：除了 1 和它本身，不能被其它自然数整除的数
• 合数：除了 1 和它本身，能被其它自然数整除的数

大于 1 的自然数，如果不是素数就是合数。2 是最小的素数，也是唯一的偶数素数。

✨ 素数判定

如果要检查自然数 n 是不是素数，只需要检查 n 是否能整除 sqrt(n) 以内的数即可。如果不能整除除 1 外的任何整数，则 n 是素数。这是因为如果 n 有一个大于 sqrt(n) 的因子，那么它必然对应一个小于 sqrt(n) 的因子，所以只需检查到 sqrt(n) 即可。

以下是试除法判定素数的代码实现：

1#include<iostream>
2#include<cmath> // 包含cmath库，用于调用sqrt函数
3using namespace std;
4
5// 函数isPrime用于判断一个整数n是否为素数
6bool isPrime(int n) {
7    // 对n小于2的情况直接返回false，因为素数定义为大于1的自然数
8    if (n < 2) {
9        return false;
10    }
11
12    // 试除法的核心思想是试着将n除以2到sqrt(n)之间的所有整数
13    // sqrt函数用于计算n的平方根，因为如果n为合数，它必有一个因子不大于其平方根
14    int rootN = sqrt(n);
15    for (int i = 2; i <= rootN; i++) {
16        // 如果n能被i整除，则n不是素数，返回false
17        if (n % i == 0) {
18            return false;
19        }
20    }
21    // 如果上面的循环完成后没有找到能整除n的数，则n是素数，返回true
22    return true;
23}
24
25int main() {
26    int number;
27    cout << "Enter a number: "; // 提示用户输入一个数
28    cin >> number; // 从标准输入读取一个整数
29
30    // 调用isPrime函数判断用户输入的数是否为素数
31    if (isPrime(number)) {
32        cout << number << " is a prime number." << endl; // 如果是素数，输出提示信息
33    } else {
34        cout << number << " is not a prime number." << endl; // 如果不是素数，输出提示信息
35    }
36    return 0; // 程序正常结束
37}

✨ 执行示例

以判断 29 是否为素数为例：

• sqrt(29) ≈ 5.38，取整为 5
• i=2：29 % 2 = 1，不能整除，继续
• i=3：29 % 3 = 2，不能整除，继续
• i=4：29 % 4 = 1，不能整除，继续
• i=5：29 % 5 = 4，不能整除，循环结束
• 结论：29 是素数

✨ 素数筛法

素数筛法是用来找出一定范围内所有素数的算法，常用的素数筛法有埃式筛法（Eratosthenes' Sieve）和欧式筛法（Euler's Sieve）。两种方法各有优势，适用于不同规模的数据范围。

试除法一次只能判断一个数，如果要找出 1~n 范围内的所有素数，逐个试除的时间复杂度高达 O(n√n)。素数筛法的思路相反：不是逐个判断，而是从已知的素数出发，批量排除它们的倍数，剩下没被排除的就是素数。

✨ 埃式筛法

埃式筛法由古希腊数学家埃拉托斯特尼提出，核心思想非常直观：如果一个数 p 是素数，那么 p 的所有倍数（2p, 3p, 4p, ...）一定不是素数。利用这个性质，我们可以从最小的素数 2 开始，逐步把所有合数"筛掉"。

具体来说，我们用一个布尔数组 isPrime[] 来记录每个数的状态。一开始假设所有数都是素数，然后从 2 开始扫描：遇到一个素数，就把它的所有倍数标记为合数。扫描完成后，数组中仍为 true 的位置就是素数。

为什么只需要筛到 sqrt(n)？ 因为如果一个合数 m ≤ n，它必然有一个不超过 sqrt(n) 的质因数。所以 sqrt(n) 以内的素数就足以筛掉所有合数。

为什么内层从 i×i 开始？ 当我们用素数 i 来筛时，i×2, i×3, ..., i×(i-1) 这些合数已经被更小的素数筛过了。例如 i=5 时，5×2=10 已被 2 筛去，5×3=15 已被 3 筛去，所以直接从 5×5=25 开始即可。

基本步骤：

1. 初始化：创建一个布尔数组，长度为 n+1（假设我们要筛选的范围是从 2 到 n），并将所有元素初始化为 true。数组的索引代表数字本身，true 代表该索引数字是素数。
2. 筛选：从第一个素数 2 开始，依次将每个素数的倍数标记为非素数（设为 false）。这个过程从 2 开始，一直进行到 sqrt(n)，因为超过 sqrt(n) 的倍数在之前已经被标记过了。
3. 收集结果：最后，数组中仍然标记为 true 的索引位置对应的数字就是素数。

埃式筛法的时间复杂度是 O(n log log n)，空间复杂度是 O(n)，适用于解决较小范围的素数筛选问题。

1#include<iostream>
2#include<cmath>
3using namespace std;
4
5// 定义一个布尔数组，用来标记每个数字是否是素数
6bool isPrime[105] = {0};
7
8// 埃拉托斯特尼筛法的实现
9void eratosthenes(int n) {
10    // 使用memset将isPrime数组的所有值初始化为true
11    memset(isPrime, 1, sizeof(isPrime));
12    int rootN = sqrt(n); // 计算n的平方根，减少不必要的遍历
13    // 从2开始遍历到n的平方根
14    for (int i = 2; i <= rootN; i++) {
15        if (isPrime[i]) { // 如果i是素数
16            // 将i的所有倍数标记为非素数
17            for (int j = i * i; j <= n; j += i) {
18                isPrime[j] = false;
19            }
20        }
21    }
22}
23
24int main() {
25    int n = 0; // 用户输入的数
26    cin >> n; // 读取用户输入
27    eratosthenes(n); // 调用埃拉托斯特尼筛法
28    // 遍历数组，打印所有标记为素数的数
29    for (int i = 2; i <= n; i++) {
30        if (isPrime[i]) {
31            cout << i << " ";
32        }
33    }
34    cout << endl;
35    return 0;
36}

✨ 执行示例

以筛出 1~30 的所有素数 为例，展示完整筛除过程：

初始状态：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30（全部标记为素数）

• i=2 是素数，从 2×2=4 开始，筛去 2 的倍数：~~4~~ ~~6~~ ~~8~~ ~~10~~ ~~12~~ ~~14~~ ~~16~~ ~~18~~ ~~20~~ ~~22~~ ~~24~~ ~~26~~ ~~28~~ ~~30~~
• i=3 是素数，从 3×3=9 开始，筛去 3 的倍数：~~9~~ ~~15~~ ~~21~~ ~~27~~（6,12等已被筛去）
• i=4 已被标记为合数，跳过
• i=5 是素数，从 5×5=25 开始，筛去 5 的倍数：~~25~~（其他倍数已被筛去）
• i=6 > sqrt(30)≈5.47，停止

剩余素数：2 3 5 7 11 13 17 19 23 29

✨ 欧式筛法（线性筛）

相对于埃式筛法，欧式筛法在执行效率上更有优势，特别是在处理大范围的数据时。它的核心优化在于确保每个合数只被它的最小质因数筛掉一次，从而避免重复标记。

欧式筛法的步骤如下：

1. 初始化：创建一个布尔数组和一个空的素数列表。
2. 筛选：遍历每个数字，如果这个数字是素数，则将其添加到素数列表中。接着，遍历素数列表，用每个素数去乘以当前数字，标记得到的乘积为非素数。关键点是，对于每个数字，只用它之前的素数进行标记，并且在遇到第一个能整除它的素数时停止标记。
3. 优化：欧式筛法确保每个合数只被它的最小质因数筛掉，从而减少了重复操作。

欧式筛法的时间复杂度接近于 O(n)，空间复杂度也是 O(n)，适用于大范围的素数筛选问题。

1#include <vector>
2#include <iostream>
3using namespace std;
4
5vector<int> primes; // 存放素数的列表
6bool isPrime[105] = {0}; // 标记数组，记录是否是素数
7
8// 线性筛法的实现
9void linearSieve(int n) {
10        // 使用memset将isPrime数组的所有值初始化为true
11        memset(isPrime, 1, sizeof(isPrime));
12    for (int i = 2; i <= n; i++) {
13        if (isPrime[i]) { // i 为素数
14                        // 将 i 添加到素数列表
15            primes.push_back(i);
16        }
17        // 用已有的素数去筛 i 的倍数
18        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
19            isPrime[i * primes[j]] = false; // 标记为非素数
20            if (i % primes[j] == 0) break; // 关键：保证最小素因子原则
21        }
22    }
23}
24
25int main() {
26        int n = 0; // 用户输入的数
27        cin >> n; // 读取用户输入
28        linearSieve(n); // 调用线性筛法
29        // 遍历数组，打印所有标记为素数的数
30        for (int i = 0; i < primes.size(); i++) {
31                cout << primes[i] << " ";
32        }
33        cout << endl;
34        return 0;
35}

✨ 执行示例

以筛出 1~20 的所有素数 为例：

关键观察：每个合数只被筛了一次。例如 12 只被 i=6 时通过 6×2 筛去，而在埃式筛法中 12 会被 2 和 3 分别筛去。

✨ 解题步骤详解

遇到涉及素数的问题时，按以下思路选择方法：

1. 判断单个数是否为素数：使用试除法，时间复杂度 O(sqrt(n))，对于 n ≤ 10^9 都够用。
2. 求 1~n 范围内所有素数：
   • n ≤ 10^6：埃式筛法足够，代码简单易写。
   • n ≤ 10^7 或更大：使用线性筛法，保证 O(n) 时间。
3. 统计范围内素数个数：先用筛法预处理，再统计或查询。
4. 判断多个数是否为素数：先用筛法预处理出一个布尔数组，之后每次查询 O(1)。

✨ 常见错误

• 将 1 判断为素数：1 既不是素数也不是合数，试除法中要特判 n < 2 返回 false。
• sqrt 精度问题：sqrt(n) 返回浮点数，可能存在精度误差。例如 sqrt(49) 可能返回 6.999...，导致漏检。建议用 i * i <= n 代替 i <= sqrt(n) 来避免这个问题。
• 埃式筛法从 i×2 开始筛：应从 i*i 开始筛，因为 i×2, i×3, ..., i×(i-1) 这些合数已经被更小的素数筛去了。虽然从 i×2 开始不影响正确性，但会影响效率。
• 线性筛忘记 break：if (i % primes[j] == 0) break; 这行是线性筛的精髓，保证每个合数只被最小质因数筛一次。忘记这行会导致时间复杂度退化。
• 数组大小不够：筛法需要开大小为 n+1 的数组，如果 n 较大要注意是否超出内存限制。

三、课后练习

编程练习

1. 含k个2的质数：L3054