首页 > 代码库 > 模板：筛素数法
模板：筛素数法
参考:http://blog.csdn.net/liukehua123/article/details/5482854
1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.
2.然后：
for( i=3; i<=sqrt(n); i+=2 )
{ if(prime[i])
for( j=i+i; j<=n; j+=i ) prime[j]=false;
}
3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。
原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质
数的倍数筛掉。
Code:
1 #include <cmath> 2 3 #define MAX_NUM 10000 4 5 6 bool * arr_prime = new bool[MAX_NUM + 1]; 7 8 for(i = 3; i <= MAX_NUM; i += 2) arr_prime[i] = true; 9 for(i = 4; i <= MAX_NUM; i += 2) arr_prime[i] = false;10 arr_prime[2] = true;11 12 int sqrt_mn = sqrt(MAX_NUM);13 14 for(i = 3; i < sqrt_mn; i += 2)15 {16 if(arr_prime[i])17 {18 for(j = i + i; j <= MAX_NUM; j += i) arr_prime[j] = false;19 }20 }21
模板：筛素数法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。