0
已解决
新手守护
（本人才学到质因数~不喜勿喷）
2024年4月27日，本人学质因数，碰见题单有1题，it is so 难，（2685）问老师后，老师说阶段4才学埃氏筛法
2
已采纳
资深守护
想要找出一个范围内的质数，用普通的枚举，并判断是否为质数的方法效率太低。我们可以用一个非常快速的方法：埃氏筛。
埃氏筛法，全称为"埃拉托斯特尼筛法"，是一种由埃及数学家埃拉托斯特尼提出的一种简单检定素数的方法。
算法流程
- 排出从1~n的数列：1、2、3、4、5、6、7、8、…
- 1不是素数，也不是合数，划掉
- 2是素数，那么 2 的倍数都是合数，把 2 的倍数划掉
- 3是素数，那么 3 的倍数都是合数，把 3 的倍数划掉
- 4是合数，那么 4 的倍数已经被 2 的倍数划掉了，跳过
- …
- 最后剩余的没有被划掉的数，都是质数
埃氏筛的优点
- 用埃氏筛的方法找出一个范围内的质数，非常高效
- 用埃氏筛的方法，可以简化代码
- 一个合数，被筛过多少次，就说明它有几个质因数。
- 比如20被2,3,5筛过，那么2,3,5是20的质因数。
- 比如8倍2筛过，那么2是8的质因数。
求采纳+点赞
0
资深守护
幺西
这不是李子墨吗
0
资深光能
学了，但忘了qwq感觉没啥大用
0
中级光能
我学过，给拓展一下：埃氏筛法又称素数筛法，是一种简单且高效的求质数的算法。它的基本思想是从2开始，将所有2的倍数标记为数，然后将下一个未标记的数(即3)标记为质数，接着将所有3的倍数标记为合数，依此类推，直到筛完所有小于或等于给定数N的数。经过一轮筛选，剩下的未标记数都是质数。懒得打字，百度了
