埃拉托斯特尼筛法
以近线性时间列出不超过 N 的所有素数
埃拉托斯特尼筛法 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
批量查找质数
有时您需要找出不超过 N 的所有质数，而不只是进行一次判断。埃拉托斯特尼筛法可以通过一次扫描找出它们。🧹
核心思想
先假设每个数都是质数。然后将找到的每个质数的倍数划掉，最后留下的就是真正的质数。
设置标记
创建一个布尔列表，其中索引 i 表示 i 是否为质数。这个数组就是筛法进行标记的画布。
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False遍历候选数
让 i 逐步增大。当您第一次遇到一个仍标记为 True 的数时，它一定是一个全新的质数，因为它没有更小的因数。
划掉倍数
对于每个质数 i，将 2i、3i、4i 等标记为非质数。这些倍数显然都以 i 为因数。
for j in range(i * i, n + 1, i):
is_prime[j] = False从 i 的平方开始
从 i*i 开始划掉，而不是从 2i 开始。所有更小的倍数都已经被更早找到的质数移除了，因此可以跳过它们。
在平方根处停止
只要 i*i 不超过 N，就继续进行筛选。超过平方根后，所有仍为 True 的标记都已经对应质数。
完整筛法
将外层扫描和内层划除操作组合起来。循环结束后，所有仍标记为 True 的索引都是已确认的质数。
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False收集质数
使用列表推导式，将完成的标记读取到一个列表中。现在您拥有了不超过 N 的所有质数
primes = [i for i, p in enumerate(is_prime) if p]为什么这么快
筛法的时间复杂度约为 O(n log log n)，接近线性。这就是它能够大幅胜过反复进行单个数检查的原因。
注意内存
标记数组所占用的内存与 N 成正比。对于非常大的上限，在分配之前请留意您的空间预算。
快速检查
回想一下内层循环中的小优化。
回顾
现在您可以构建一个筛法，以接近线性的时间列出不超过 N 的所有质数：从每个质数的 i*i 开始，并在平方根处停止。✅
常见问题解答
「埃拉托斯特尼筛法」课时是免费的吗？
是的 — 「埃拉托斯特尼筛法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「埃拉托斯特尼筛法」这节课中我会学到什么？
以近线性时间列出不超过 N 的所有素数 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「埃拉托斯特尼筛法」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。