埃拉托斯特尼筛法可视化工具
在数字网格上动态演示埃拉托斯特尼筛法——标记质数、划掉合数，支持逐步操作。直接在浏览器中运行。
伪代码
Run an operation to see its steps.
Avg · Worst
使用方法
- 1 输入上限 n(最大 150),然后点击“Run sieve”。
- 2 观察每个质数被标记的过程,随后它的所有倍数会被划掉,因为它们都是合数。
- 3 使用上一步和下一步按钮逐步查看,或点击“Random”随机选择另一个上限。
- 4 绿色格子代表质数,灰色格子代表合数。
为什么使用此工具
- 理解为什么筛法在处理每个质数 p 时,只需从 p² 开始标记即可。
- 直观看到合数被逐一划掉,最终只留下高亮显示的质数。
- 理解该算法接近线性的时间复杂度 O(n log log n)。
- 完全在你的浏览器中运行,无需注册,无需上传任何内容。
常见问题
什么是埃拉托斯特尼筛法?
这是一种古老的算法,用于找出小于等于给定上限 n 的所有质数:反复取出下一个尚未标记的数字(即质数),然后将它的所有倍数标记为合数。
这种筛法算法的时间复杂度是多少?
时间复杂度为 O(n log log n),空间复杂度为 O(n)——比逐个检验每个数字是否为质数要快得多。
为什么标记要从 p² 开始,而不是从 2p 开始?
因为 p 的所有小于 p² 的倍数(如 2p、3p 等)都已经含有一个更小的质因数,并且在处理该质因数时就已经被标记过了,所以从 p² 开始可以避免重复劳动。
1 是质数吗?
不是。1 只有一个因数,因此根据定义它既不是质数也不是合数——该筛法算法会将它视为非质数。
什么是 埃拉托斯特尼筛法可视化工具？
埃拉托斯特尼筛法可视化工具动态演示了这一经典的质数查找算法：从 2 开始，每次将尚未标记的最小数字标记为质数，再划掉该数字的所有倍数（即合数），最终留下的就是小于等于 n 的所有质数。
功能特性
逐步动画演示
观看 2、3、5……的倍数被依次划去，最终只留下素数。
复杂度
时间复杂度：O(n log log n)。空间复杂度：布尔筛数组占用 O(n)。
100% 隐私保护
完全在你的浏览器中运行——不会上传任何数据。
示例
Input
primes up to 30Output
2, 3, 5, 7, 11, 13, 17, 19, 23, 29常见使用场景
-
1
快速列出素数
高效生成小于给定上限的所有素数。
-
2
为问题预先计算
为数论或竞赛编程问题构建素数表。
-
3
理解筛法的思路
了解为什么标记倍数比逐个数字进行素性检验更高效。
Zerethon 的埃拉托斯特尼筛法可视化工具会在你的浏览器中动态演示如何找出小于等于给定上限 n 的所有素数，将每个素数的倍数标记为合数。该筛法的时间复杂度为 O(n log log n)，空间复杂度为 O(n)——比逐一检测每个数字是否为素数快得多。
- 分类
- 算法
- 价格
- 免费
- 隐私
- 基于浏览器
- 注册
- 无需
参考资料
- Sieve of Eratosthenes — Wolfram MathWorld — Wolfram MathWorld
- Sieve of Eratosthenes — Wikipedia
隐私
除非另有说明，否则你的数据永远不会离开浏览器。埃拉托斯特尼筛法可视化工具 完全在客户端运行 — 无需上传服务器，不记录日志，不追踪你输入的内容。
刚接触？阅读包含 Big-O 分析的分步讲解： 了解 Number Theory →
在 Zerethon Social 上创作、分享与成长
免费注册。赚取积分，收集成就，与全球创作者建立联系。