Eratosthenes 筛法
| 埃拉托斯特尼筛法 | |
|---|---|
| 术语名称 | 埃拉托斯特尼筛法 |
| 英语名称 | seive of Eratosthenes |
| 别名 | 埃拉托色尼筛法, 埃氏筛, 爱氏筛, 厄拉多塞筛法 |
埃拉托斯特尼筛法(seive of Eratosthenes)，简称埃氏筛，是找出小于某正整数的全部质数的算法。
算法
列出所有正整数，删去 1 后，每次取出最前一个未被删除的数，并删除其所有范围内的倍数，直到所有的数字都被取出或删除。
（限制范围时可以只进行到总数的平方根，因为不可能再出现某个数是更大质数的积）
伪代码
过程 埃氏筛
别名 eratosthenes_seive
参数 n : 正整数 // 范围上限
返回 primes : 正整数的列表 // 质数列表
令 p₁~ₙ 为 未遍历
令 p₁ 为 已遍历
循环 k
当 k ≤ n 时 ❶
执行
如果 k 已遍历 那么
继续下轮循环
将 k 加入列表 primes
记 j, q ← k // 当前遍历位置及质数
循环 j 当 j ≤ n 时
令 pⱼ 为 已遍历
继续循环 j ← j + q
继续循环 k ← k + 1
返回 primes❶ 这里可以改为 k² ≤ n 。
复杂度
主要操作是遍历倍数，因此是对每个质数，按其倍数的个数求和，即 [math]\displaystyle{ \frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} \sim n \log\log n }[/math] 。[1]
| 情况 | 复杂度估计 | 渐近级别 | 发生条件 |
|---|---|---|---|
| 平均情况 | [math]\displaystyle{ \sim n \log \log n }[/math] | [math]\displaystyle{ O(n \log \log n) }[/math] | - |
| 最好情况 | |||
| 最坏情况 |
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |