admin 管理员组文章数量: 1086019
2024年4月22日发(作者：date函数将数字转化为年月日)
求素数的三种方法
素数的定义：
素数也叫质数。一个大于1的自然数，除了1和它本身之外，不能被其它自然数整除的数叫
做素数；能被其它自然数整除的数叫做合数。规定，1既不是质数也不是合数。
法一：试除法（判断素数）
让
N
被
2
到
N
除，如果
N
能被其中任何一个整数整除，则提前结束循环，
N
不是素数；
如果
N
不能被其中任何一个整数整除，则
N
是素数。
代码实现：
法二：埃氏筛法（求一个范围中所有素数）
试除法可以用来判断一个数是否为素数，如果用来求某一范围内所有素数的话，效率就比较
低。埃氏筛法是用来解决这类问题的古老而简单高效的方法，可以快速找到
[2,n]
中的所有
素数。具体操作是这样的：从2开始寻找素数，每次找到一个素数后就将它的倍数全部筛
掉，并将该素数存储到另一个数组中，不断循环，直到原数组为空。
法三：欧拉筛法（埃氏筛法的优化版）
埃氏筛法中，由于一个数可以既是一个素数的倍数，又是另一个素数的倍数，可以发现这会
出现重复标记的情况，即同一个数被筛掉了不止一次，浪费操作了。
欧拉筛法就是在埃氏筛法的基础上多了判断的步骤，从而消失了这种重复标记的情况，核心
思想是用合数中的一个因数筛掉这个合数。
具体操作为：利用已经求得的素数，第一重循环将区间内的数从小到大遍历，第二重循环将
以求得的素数从小到大遍历，将这个数和素数的乘积标记为合数。如果一个数能被素数整除，
跳出循环。
版权声明：本文标题：素数常见的算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1713729619a648845.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论