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

素数搜索动画 - 试除法与埃拉托斯特尼筛法动态比较

数学 算法 动画 搜索 算法 素数
42
0
0
0
慢适中快
试除步骤: 0 筛法步骤: 0 质数: 0
试除法 (Trial Division)
O(n√n)
准备就绪 — 逐个测试每个数字的除数
埃拉托斯特尼筛法
O(n log log n)
准备就绪 — 使用筛子批量标记合数
图例: 未检查 检查中 当前质数/焦点 质数 合数 标记中
常见问题与知识点
素数（质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的数。例如：2、3、5、7、11、13、17、19、23、29等都是素数。注意，数字1既不是素数也不是合数。素数在数论和密码学中有着至关重要的地位。
试除法判断单个数字n是否为素数的时间复杂度为O(√n)。如果对2到N的所有数字都用试除法判断，总时间复杂度约为O(N√N)。对于较大的N（如N=10^6），这意味着需要进行数亿次除法运算，效率较低。但试除法的优势是实现简单，且对于单个大数的素性测试可以通过优化（如只测试到√n、跳过偶数等）来加速。
筛法的核心思想是"用已知质数去标记其倍数为合数"。具体步骤：①列出2到N的所有整数；②从最小的数2开始，2是质数，将2的所有倍数（4,6,8,...）标记为合数；③找到下一个未被标记的数（3），它是质数，将其所有倍数标记为合数；④重复此过程，直到当前质数的平方超过N；⑤所有未被标记的数即为素数。这种方法避免了大量的除法运算，效率远高于试除法。
筛法中，对于每个质数p，需要标记n/p个倍数。所有质数的n/p之和为n×(1/2+1/3+1/5+1/7+...)，即n乘以所有质数的倒数之和。根据数论中的默滕斯定理，质数倒数和近似为log log n + M（M为常数）。因此总操作次数约为O(n log log n)，这比试除法的O(n√n)要快得多。对于n=10^6，筛法仅需约10^7次操作，而试除法需要约10^9次。
试除法：优点是实现简单、空间复杂度O(1)；缺点是对于批量素数搜索效率低。适合判断单个大数是否为素数，配合优化（仅测试到√n、6k±1规则等）可在合理时间内判断相当大的数。
筛法：优点是批量搜索效率极高；缺点是需要O(n)的额外空间存储标记数组。适合需要找出某个范围内所有素数的场景，如生成素数表、解决算法竞赛问题等。对于n很大（如10^9），分段筛法可以平衡空间需求。
素数在现代密码学中扮演核心角色。RSA加密算法的安全性基于大素数乘积的因数分解困难性——两个大素数相乘很容易，但从乘积中分解出原始素数却极其困难。RSA密钥生成需要随机选择两个大素数（通常数百位），其乘积作为公钥的一部分。Diffie-Hellman密钥交换和椭圆曲线密码学(ECC)也依赖素数的数学性质。这就是为什么高效的素性测试算法（如Miller-Rabin）在计算机安全领域如此重要。
对于大数（如数百位），试除法完全不适用。实践中使用概率素性测试，如Miller-Rabin测试。该算法基于费马小定理的扩展，通过随机选择多个底数进行测试，可以在O(k log³ n)时间内以极高的概率判断n是否为素数（k为测试轮数，通常20-40轮即可将错误概率降至10^-12以下）。对于需要确定性结果的场景，可使用AKS算法（理论上多项式时间）或ECPP（椭圆曲线素性证明）。
🔧 相关工具