首页 > 代码库 > 筛法求素数
筛法求素数
问:求2000以内的素数?
筛法求素数 和 暴力
时间复杂度
筛法求素数:O(N^2)
暴力:O(N^N)
原理:
去掉1,最小的数是素数,然后将最小数的倍数全部去掉,直到最小的数到达范围为止
用筛子把非素数全部筛出去。
bool是C++中的一种数据类型 0代表false 1代表true bool一定要初始化
代码:
1 #include <stdio.h> 2 #define MAX 5000 3 4 int main() 5 { 6 bool a[MAX]; 7 int i, j; 8 for(i = 0;i < MAX;i++) 9 { 10 a[i] = true; 11 } 12 a[0] = false; 13 a[1] = false; 14 15 for(i = 2;i < MAX;i++) 16 { 17 if(!a[i]) 18 continue; 19 for(j = 2*i;j < MAX;j = j + i) 20 { 21 a[j] = false; 22 } 23 } 24 for(i = 2;i < MAX;i++) 25 { 26 if(a[i]) 27 printf("%d ",i); 28 } 29 30 return 0; 31 }
筛法求素数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。