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

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

12
0
0
0

埃拉托斯特尼筛法

Sieve of Eratosthenes
可视化素数筛选过程
当前: - 素数: 0 合数: 0 进度: 0%
未处理 正在筛选 合数(被筛除) 素数(已确认) 数字1(特殊)
算法日志 0 条
点击"开始筛选"查看动画过程
知识点 & 常见问题

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种古希腊数学家埃拉托斯特尼提出的寻找素数的经典算法。其核心思想是：从小到大遍历每个数，如果它没有被标记为合数，则它是素数，然后将它的所有倍数标记为合数。这个过程像筛子一样，将合数逐步筛除，最终留下素数。该算法效率较高，时间复杂度为 O(n log log n)。

因为任何一个合数 n ≤ N，必定有一个质因数 ≤ √N。如果 n 的所有质因数都大于 √N，那么它们的乘积将大于 N，产生矛盾。因此，当我们用 ≤ √N 的所有素数筛过之后，剩余未被标记的数必定都是素数。这也是为什么算法在 p² > N 时可以提前终止。

对于素数 p，小于 p² 的倍数（如 2p, 3p, ..., (p-1)p）必定包含比 p 更小的质因数，因此它们已经被更小的素数标记过了。例如 p=5 时，10=2×5（被2标记），15=3×5（被3标记），20=4×5（被2标记），所以直接从 25=5² 开始标记。这一优化显著减少了重复标记次数。

埃拉托斯特尼筛法的时间复杂度为 O(n log log n)，空间复杂度为 O(n)。这源于调和级数的性质：∑p≤√n n/p ≈ n × (log log n + M)，其中M是常数。对于大多数实际应用（n ≤ 10⁷），这个算法表现非常优异。此外还有线性筛法（欧拉筛）可以达到 O(n) 的时间复杂度，但实现稍复杂。

试除法：对每个数 n，逐个测试是否能被小于 √n 的数整除，单次判定时间复杂度 O(√n)，批量找出所有素数需要 O(n√n)。
筛法：一次性处理整个范围，通过标记倍数的方式批量筛除合数，总时间复杂度 O(n log log n)，在需要找出一个范围内所有素数时远优于试除法。

筛法广泛应用于：密码学（RSA密钥生成需要大素数）、哈希表设计（选择素数大小的表）、数论研究、竞赛编程（ACM/LeetCode中素数相关问题）、以及伪随机数生成等场景。预处理素数表后可以O(1)判断一个数是否为素数（在表范围内）。

常见优化包括：① 只筛奇数（除2外偶数都不是素数，可将空间减半）；② 位图压缩（用bit表示每个数的状态，节省内存）；③ 分段筛法（将大范围分成小段处理，适合N极大的情况）；④ 线性筛/欧拉筛（保证每个合数只被其最小质因数筛除一次，达到O(n)）。

本工具支持 N 从 10 到 600 的范围。限制上限是因为：① 超过600后网格单元格过多，影响视觉体验；② DOM元素过多会导致动画性能下降。对于更大范围的素数需求，建议使用专业数学软件或编程实现。对于教学和可视化目的，10-200是最佳范围。
🔧 相关工具