首页 > 代码库 > 关于埃拉托色尼筛选法的整理(质数问题)
关于埃拉托色尼筛选法的整理(质数问题)
求素数的问题也有不少的算法,埃拉托色尼筛选法应该算是时间复杂度不大的一种算法。。。。
比如要求从1到n范围内的素数表,基本算法思想就是从第一个质数2开始,把2的所有倍数标记为非素数,然后进入到3,把3的所有倍数标记为非素数,然后跳过4(因为4是2的倍数而且已经被标记为非素数了),然后进入到5,把5的所有倍数标记为非素数,循环直至结束。
以上算法还可以继续改进,那就是最外层循环可以只遍历到根号n就行了。因为大于根号n的数要么是素数,要么就有一个小于根号n的因数(而这是不可能发生的,因为如果它有小于根号n的因数的话,那他就已经被筛掉了)。
代码如下所示:
1 #include<iostream> 2 #include<cstdio> 3 #define N 10000 4 using namespace std; 5 int main()//从2开始往后看,凡是2,3,5的倍数全部筛掉 6 { 7 int i,j,k,a[N]; 8 for(i=2;i<N;i++) 9 a[i]=1; 10 for(i=2;i<N;i++) 11 { 12 if(a[i]) 13 for(j=i;i*j<N;j++) 14 { 15 k=i*j; 16 a[k]=0; 17 } 18 } 19 for(i=2;i<N;i++) 20 if(a[i]) 21 printf("%d ",i); 22 return 0; 23 }
关于埃拉托色尼筛选法的整理(质数问题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。