1. 概述
素数一直是数学和计算机科学中非常有趣的研究对象。尽管数学家们一直试图找到一个简洁、有限的公式来生成所有素数，但至今仍未成功。因此，人们依赖于算法和计算能力来寻找素数。这些算法有的效率较高，有的则相对耗时。
本文将介绍一些经典的查找素数的算法，从最古老的到较新的方法逐一讲解。
2. 埃拉托色尼筛法（Sieve of Eratosthenes）
✅ Sieve of Eratosthenes 是查找小于等于 n 的所有素数的最古老且简单有效的方法之一。
其核心思想是：从 2 开始，将每一个素数的所有倍数标记为合数。这样逐步筛去合数，剩下的就是素数。
原理详解
- 初始化一个大小为 n 的布尔数组 A，初始值为 true（表示是素数）。
- 从 2 开始，遍历到 √n：
- 如果 A[i] 为 true，则 i 是素数。
- 从 i² 开始，将所有 i 的倍数标记为 false（即合数）。
- 最终，数组中值为 true 的下标即为所有小于 n 的素数。
⚠️ 为什么从 i² 开始？
因为在遍历到 i 时，i 的所有比 i 小的倍数已经被前面的素数筛掉了。例如，当 i=7 时，49 是第一个未被筛掉的 7 的倍数。
算法伪代码
algorithm FindPrimesEratosthenes(n):
A <- new boolean[n] initialized to true
for i from 2 to sqrt(n):
if A[i] is true:
j <- i * i
while j <= n:
A[j] <- false
j <- j + i
return indices where A[i] is true
时间复杂度分析
- 外层循环运行 O(√n) 次。
- 内层循环对每个素数 i 来说，运行次数为 O(n / i)。
- 总时间复杂度为：
$$ O(n \log \log n) $$
这是目前已知最高效的基础筛法之一。
3. 桑达拉姆筛法（Sieve of Sundaram）
✅ Sundaram 筛法也是一种筛法，但它只筛掉特定形式的合数，最终通过变换得到所有奇素数。
核心思想
- 找出所有形如 i + j + 2ij 的数（其中 1 ≤ i ≤ j，且 i + j + 2ij ≤ n），并筛掉它们。
- 剩下的数乘以 2 再加 1，得到所有小于 2n+1 的奇素数。
- 注意：这个方法不会生成 2，因此需要手动添加。
算法伪代码
algorithm FindPrimesSundaram(n):
k <- floor((n - 1) / 2)
A <- new boolean[k + 1] initialized to true
for i from 1 to sqrt(k):
j <- i
while i + j + 2 * i * j <= k:
A[i + j + 2 * i * j] <- false
j <- j + 1
T <- indices where A[i] is true
T <- 2 * T + 1
add 2 to T
return T
时间复杂度分析
- 外层循环运行 O(√n) 次。
- 内层循环平均运行 O(n / i) 次。
- 总时间复杂度为：
$$ O(n \log n) $$
虽然比 Eratosthenes 筛法慢，但其思想独特，适合教学和理解。
4. 阿特金筛法（Sieve of Atkin）
✅ Atkin 筛法是目前已知渐进最快的素数筛法之一，但实现复杂度高。
核心思想
- 利用特定的二次方程解来标记可能的素数。
- 通过模 60 分类处理，避免重复标记。
- 最后筛除平方数的倍数，并返回结果。
算法伪代码（简化）
algorithm FindPrimesAtkin(n):
A <- new boolean[n] initialized to false
// 根据不同二次方程标记候选素数
for x from 1 to sqrt(n):
for y from 1 to sqrt(n) step 2:
m = 4*x^2 + y^2
if m <= n and (m mod 60 in {1, 13, 17, 29, 37, 41, 49, 53}):
A[m] = not A[m]
// 类似处理其他方程...
// 筛除平方数的倍数
for m from 2 to sqrt(n):
if A[m] is true:
for multiple from m^2 to n step m^2:
A[multiple] = false
// 添加 2, 3, 5
return [2, 3, 5] + indices where A[i] is true
时间复杂度分析
- 通过巧妙的数学方法和分类处理，Atkin 筛法的理论时间复杂度为：
$$ O(n) $$
✅ 优点： 渐进最优，适合大规模素数生成。
❌ 缺点： 实现复杂，常数因子较大，小规模数据反而慢。
5. 总结
| 算法名称 | 时间复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|
| 埃拉托色尼筛法 | O(n log log n) | ✅ 简单 | 中小规模数据 |
| 桑达拉姆筛法 | O(n log n) | ✅ 简单 | 教学/理解 |
| 阿特金筛法 | O(n) | ❌ 复杂 | 大规模数据 |
📌 选择建议：
- 数据量小或教学用途：使用 Eratosthenes 筛法。
- 理解筛法思想：Sundaram 是个好例子。
- 高性能需求、大规模数据：考虑 Atkin 筛法（注意其实现复杂度）。
📌 踩坑提醒：
- 实现筛法时注意边界条件，尤其是数组索引和终止条件。
- Atkin 筛法虽然理论复杂度最优，但实际中不一定最快，尤其是在 n 不太大时。
如需进一步优化性能，可考虑分段筛法（Segmented Sieve）或并行化实现。