埃拉托斯特尼筛法
算法起源
埃拉托斯特尼筛法（Sieve of Eratosthenes）是古希腊数学家埃拉托斯特尼在公元前3世纪提出的一种简单筛法，用于查找不超过给定整数n的所有质数。
算法原理
- 从最小的质数2开始，依次标记其倍数（4, 6, 8, ...）为合数
- 处理完2后，移动到下一个未被标记的数（3），标记其所有倍数
- 重复上述过程，直到处理完√n范围内的所有数
- 剩余未被标记的数即为质数
时间复杂度：O(n log log n)
算法特点
- 实现简单直观，易于理解
- 效率较高，适合大规模筛选（n ≤ 107）
- 需要O(n)内存空间存储标记数组
- 存在重复标记合数的问题（如6会被2和3重复标记）
埃拉托斯特尼筛法实现 (C++)
C++
// 使用埃筛获取n以内的所有素数 const int MAXN = 10000000; // 最大范围 bool isPrime[MAXN + 1]; // 标记数组 vector<int> primes; // 存储素数 void eratosthenesSieve(int n) { // 初始化标记数组，全部设为true for (int i = 2; i <= n; i++) { isPrime[i] = true; } // 从2开始筛 for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { // 标记i的所有倍数为合数 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 收集所有素数 for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.push_back(i); } } }
欧拉线性筛法
算法起源
欧拉筛法（Euler's Sieve）由著名数学家欧拉改进，解决了埃筛重复标记的问题，每个合数仅被其最小质因数筛除一次。
算法原理
- 维护一个质数列表，初始为空
- 从2开始枚举每个数，如果是质数则加入列表
- 用当前数与已知质数列表中的质数相乘，标记其乘积为合数
- 当当前数能被某个质数整除时终止内层循环
时间复杂度：O(n)
算法特点
- 时间复杂度达到理论最优的O(n)
- 每个合数只被标记一次，效率更高
- 适合更大范围（n ≤ 107~108）的素数筛选
- 实现稍复杂，需要理解其数学原理
- 可同时获得每个数的最小质因数
欧拉线性筛法实现 (C++)
C++
// 使用线性筛获取n以内的所有素数 const int MAXN = 100000000; // 更大范围 bool isPrime[MAXN + 1]; // 标记数组 vector<int> primes; // 存储素数 void eulerSieve(int n) { // 初始化标记数组，全部设为true for (int i = 2; i <= n; i++) { isPrime[i] = true; } for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.push_back(i); // i是素数，加入列表 } // 用当前数i与已知素数相乘 for (int j = 0; j < primes.size(); j++) { int p = primes[j]; if (i * p > n) break; // 超过范围 isPrime[i * p] = false; // 标记合数 // 关键：当i能被p整除时停止 if (i % p == 0) { break; } } } }
两种筛法对比
| 特性 | 埃拉托斯特尼筛法 | 欧拉线性筛法 |
|---|---|---|
| 时间复杂度 | O(n log log n) | O(n) |
| 空间复杂度 | O(n) | O(n) |
| 标记次数 | 每个合数被标记多次 | 每个合数仅被标记一次 |
| 实现复杂度 | 简单 | 较复杂 |
| 适合范围 | n ≤ 107 | n ≤ 108 |
| 额外功能 | 仅素数判断 | 可同时求最小质因数 |
如何选择？
对于大多数情况，埃筛因其简单高效已足够使用。当需要处理更大范围（n > 107）或需要获取每个数的最小质因数时，应选择欧拉线性筛。