|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
寻找素数：欧拉筛法（Sieve of Euler）
缘起
欧拉筛法（Sieve of Euler）是一种计算一定范围内所有素数的算法。
它是基于埃拉托斯特尼筛法的一个改进（没听过的鱼油，请先学习 -> 寻找素数：埃拉托斯特尼筛法（Sieve of Eratosthenes））。
两者的主要区别在于它保证了每个合数只被它的最小质因数筛去，从而减少了重复操作，提高了筛选效率。
这个筛法的名字来源于著名的数学家欧拉，但并不是由欧拉本人提出的。
它是近年来计算机时代的产物，是一种更适合于计算机运算的筛法。
步骤
下面，小甲鱼给大家阐述欧拉筛法的步骤：
1. 创建一个列表，表示每个数字是否是素数。初始化时，我们先假设所有的数都是素数（除了 0 和 1，地球人都知道它们不是素数）。
2. 从最小的素数 2 开始，如果一个数是素数，就把它的所有倍数标记为非素数。这一步被称为 “筛选”，因为我们在筛选出所有由当前素数产生的合数。
3. 不同于埃拉托斯特尼筛法，欧拉筛法在筛选合数时，每个合数只会被它的最小质因数筛去。这是通过在内部循环中增加一个判断实现的：如果当前数 i 能被素数整除，就跳出循环。
4. 找到下一个仍被标记为素数的数字，然后把它的所有倍数标记为非素数。
5. 重复第 4 个步骤，直到所有的数都被处理过。
6. 最后，仍被标记为素数的数字就是所有的素数。
这种方法的主要优点是效率高，因为每个合数只被筛去一次，而述埃拉托斯特尼筛法每个合数将被筛选若干次。
演示
实现
|
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-5-23 04:57:06
置顶卡
千斤顶
显身卡
发表于 2024-3-28 15:12:37
学习学习
发表于 2023-6-17 23:46:44
