首页 > 代码库 > 素数筛选法
素数筛选法
当一个数不算大的时候，可以用普通的求素数的方法去求，但是如果一个数过大的话，就像让求1-十亿之间素数的个数，普通方法就不行了，这事就需要用到素数筛选法，他的时间复杂度是O(n),尽管不算很好，但是，也算是目前为止比较快的一种方法了，它是以空间换取时间，现在的计算机，空间有的是，但是时间是非常珍贵的。效率问题特别重要。他的原理就是标记，防止重复判断，这样提高了效率。就像2是素数，所有是2的倍数的肯定都不是素数，这时候标记上，接着判断3是素数，所有是3的倍数的都肯定不是素数，这时就要标记上，以此下去，执行到根下(总数)，这样就会得到一个素数表，所有没有被标记的都是素数，下面是具体的代码实现，代码里面有注释。写的很清楚。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #define MAX 1000000000//定义一个数组长度 5 bool prime[MAX + 1];//素数表 6 int main() 7 { 8 int i, j, count = 0;//count为计数器 9 memset(prime, true, sizeof(prime));//初始化，将prime数组全部都初始化为true10 prime[0] = prime[1] = false; prime[2] = true;//0，1都不是素数，所以为false，2是素数，所以为true11 for(i = 2; i * i <= MAX; i ++)/*从2开始进行遍历， i * i <= MAX 就等价于 i < sqrt(MAX);但是前者更不容易出错12 具体为什么是sqrt就不用说了吧，普通的方法中也有这个*/ 13 {14 if(prime[i])//如果没有被标记的话将它的倍数的数标记(标记就是将它赋值为false)15 {16 for(j = i * i; j <= MAX; j += i)//因为是从2开始的，所以j = i * i 就行了，最小的一个他的倍数的就是i * i了，不可能有比这个更小的了17 prime[j] = false;//标记为false18 }19 }20 for(i = 2; i <= MAX; i ++)//遍历一下，找出所有的素数来21 if(prime[i])22 count ++;//如果没有被标记，计数器++23 printf("count is :%d\n", count);24 return 0;25 }
这时最基础的，当然还可以进行改进，改进的越多，执行效率就越快，例如:因为偶数不可能为素数，它是肯定能被2整除的，所以可以舍掉所有的偶数，这样会减少一半的时间，当然空间也会减少一半，如果十亿的话，开个5亿的数组就行了，for循环中的i 应该是从3开始了,然后一次加2，这样标记会更快，具体代码就不实现了。大致原理差不多。这时一个非常基础的算法。素数也是用到的比较多的。当然也可以琢磨点在改进改进，目前为止我没有想到更好的，如果有哪位大神有更好的方法，麻烦留一下言告知一下,谢谢！
素数筛选法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。