Eratosthenes 筛法
| 埃拉托斯特尼筛法 | |
|---|---|
| 术语名称 | 埃拉托斯特尼筛法 |
| 英语名称 | sieve of Eratosthenes |
| 别名 | 埃拉托色尼筛法, 埃氏筛, 爱氏筛, 厄拉多塞筛法 |
Eratosthenes 筛法(sieve of Eratosthenes)，简称埃氏筛，是找出小于某正整数的全部质数的算法。
原理
对一个大于 1 的正整数，它是合数当且仅当它有一个小于其的质因子。更精确地，当且仅当它有一个不大于其算术平方根的质因子。
算法
列出所有正整数，删去 1 后，每次取出最前一个未被删除的数，并删除其所有范围内的倍数，直到所有的数字都被取出或删除。
（限制范围时可以只进行到总数的平方根，因为不可能再出现某个数是更大质数的积）
伪代码
过程 埃氏筛
别名 eratosthenes_sieve
参数 n : 正整数 // 范围上限
返回 primes : 正整数的列表 // 质数列表
令 p₁~ₙ 为 未遍历
令 p₁ 为 已遍历
循环 k
当 k ≤ n 时 ❶
执行
如果 k 已遍历 那么
继续下轮循环
将 k 加入列表 primes
记 j ← k, q ← k // 当前遍历位置及质数
循环 j 当 j ≤ n 时 ❷
令 pⱼ 为 已遍历
继续循环 j ← j + q
继续循环 k ← k + 1
返回 primes❶ 原理上通常使用 k ≤ n 。常见变体中这里可以改为 k² ≤ n ，并在最后再使用循环收集其余的未遍历整数。
❷ 一般用于演示的算法中，不把质数收集到列表，而是保持质数为“未标记”状态，以便于可视化。在这个伪代码里，质数是通过是否在列表中体现的，不需要保持其状态，所以把质数一起标记了。
复杂度
主要操作是遍历倍数，因此是对每个质数，按其倍数的个数求和，即 [math]\displaystyle{ \frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + \dots \sim n \log\log n }[/math] 。[1]
| 情况 | 复杂度估计 | 渐近级别 | 发生条件 |
|---|---|---|---|
| 平均情况 | [math]\displaystyle{ \sim n \log \log n }[/math] | [math]\displaystyle{ O(n \log \log n) }[/math] | - |
| 最好情况 | |||
| 最坏情况 |