对于大于 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 是否为素数为例：
素数筛法是用来找出一定范围内所有素数的算法，常用的素数筛法有埃式筛法（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 开始即可。
基本步骤：
埃式筛法的时间复杂度是 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（全部标记为素数）
剩余素数：2 3 5 7 11 13 17 19 23 29
相对于埃式筛法，欧式筛法在执行效率上更有优势，特别是在处理大范围的数据时。它的核心优化在于确保每个合数只被它的最小质因数筛掉一次，从而避免重复标记。
欧式筛法的步骤如下：
欧式筛法的时间复杂度接近于 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 的所有素数 为例：
| i | isPrime[i]? | 加入primes | 筛除的合数（i × primes[j]） | break原因 |
|---|---|---|---|---|
| 2 | 是 | primes={2} | 2×2=4 | 2%2==0 |
| 3 | 是 | primes={2,3} | 3×2=6, 3×3=9 | 3%3==0 |
| 4 | 否 | - | 4×2=8 | 4%2==0 |
| 5 | 是 | primes={2,3,5} | 5×2=10, 5×3=15 | 5×5=25>20 |
| 6 | 否 | - | 6×2=12 | 6%2==0 |
| 7 | 是 | primes={2,3,5,7} | 7×2=14 | 7×3=21>20 |
| 8 | 否 | - | 8×2=16 | 8%2==0 |
| 9 | 否 | - | 9×2=18 | 9×3=27>20 |
| 10 | 否 | - | 10×2=20 | 10%2==0 |
| ... | ... | ... | ... | ... |
关键观察：每个合数只被筛了一次。例如 12 只被 i=6 时通过 6×2 筛去，而在埃式筛法中 12 会被 2 和 3 分别筛去。
遇到涉及素数的问题时，按以下思路选择方法：
n < 2 返回 false。sqrt(n) 返回浮点数，可能存在精度误差。例如 sqrt(49) 可能返回 6.999...，导致漏检。建议用 i * i <= n 代替 i <= sqrt(n) 来避免这个问题。i*i 开始筛，因为 i×2, i×3, ..., i×(i-1) 这些合数已经被更小的素数筛去了。虽然从 i×2 开始不影响正确性，但会影响效率。if (i % primes[j] == 0) break; 这行是线性筛的精髓，保证每个合数只被最小质因数筛一次。忘记这行会导致时间复杂度退化。