无需登录 数据私有 本地保存

埃拉托斯特尼筛法动画 - 素数的筛选过程

数学 算法 动画 数学 筛选 素数
15
0
0
0
未处理 当前质数 正在筛除 合数（已筛除） 质数（已确认）
速度：
👆 点击「播放」开始筛选动画，或点击「单步」逐步观察
-
数字总数
0
已确认质数
0
已筛除合数
-
待处理
已找到的质数： （0个）
尚未开始筛选...
常见问题
埃拉托斯特尼筛法（Sieve of Eratosthenes）是最古老的素数筛选算法之一，由古希腊数学家埃拉托斯特尼在公元前3世纪提出。它的核心思想是：从最小的质数开始，逐个划掉它的所有倍数，剩下的就是质数。时间复杂度为 O(n log log n)，对于中等规模的数据非常高效。
对于质数 p，所有小于 p² 的 p 的倍数（如 2p、3p、…、(p-1)p）都已经被比 p 更小的质数筛除过了。例如 p=5 时，10（2×5）、15（3×5）、20（4×5）已经分别被质数 2 和 3 标记为合数，因此只需从 5×5=25 开始筛除。
当当前质数 p 满足 p² > N 时（即 p > √N），所有剩余未标记的数字都是质数，算法可以提前终止。例如 N=100 时，√100=10，只需筛到质数 7（7²=49≤100），而质数 11 的平方 121>100，此时剩下的未标记数全部是质数。
不是。1 既不是质数也不是合数。根据现代数学定义，质数必须有且仅有两个不同的正因数（1 和它本身），而 1 只有一个因数，因此被排除在质数之外。在本工具中，数字范围从 2 开始。
2 到 100 之间共有 25 个质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97。你可以用本工具直观地看到它们被筛选出来的完整过程。
🔧 相关工具