查看“︁Eratosthenes 筛法”︁的源代码

[[分类:整除理论]]
[[分类:质数分布问题]]
[[分类:数论算法]]
[[分类:以 Eratosthenes 命名]]
{{InfoBox
|name=埃拉托斯特尼筛法
|eng_name=seive of Eratosthenes
|aliases=埃拉托色尼筛法,埃氏筛,爱氏筛,厄拉多塞筛法
}}
'''<ins>埃拉托斯特尼</ins>筛法'''('''seive of Eratosthenes''')，简称'''<ins>埃氏</ins>筛'''，是找出小于某正整数的全部[[质数]]的算法。

== 算法 ==

列出所有正整数，删去 1 后，每次取出最前一个未被删除的数，并删除其所有范围内的倍数，直到所有的数字都被取出或删除。

（限制范围时可以只进行到总数的平方根，因为不可能再出现某个数是更大质数的积）

=== 伪代码 ===

<syntaxhighlight>
过程 埃氏筛
别名 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
</syntaxhighlight>

❶ 这里可以改为 <syntaxhighlight inline>k² ≤ n</syntaxhighlight> 。

=== 复杂度 ===

主要操作是遍历倍数，因此是对每个质数，按其倍数的个数求和，即 <math>\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} \sim n \log\log n</math> 。<ref>https://www.geeksforgeeks.org/how-is-the-time-complexity-of-sieve-of-eratosthenes-is-nloglogn/</ref>

{{固定复杂度|<math>\sim n \log \log n</math>|<math>O(n \log \log n)</math>}}


{{整除与质数}}