首页 > 代码库 > 素数筛子算法
素数筛子算法
描述
现在给你一个正整数N,要你快速的找出在2.....N这些数里面所有的素数。
输入
给出一个正整数数N(N<=2000000)
但N为0时结束程序。
测试数据不超过100组
输出
将2~N范围内所有的素数输出。两个数之间用空格隔开
样例输入
5
10
11
0
样例输出
2 3 5
2 3 5 7
2 3 5 7 11
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #define N 2000001 5 6 int main(){ 7 int i; 8 int j; 9 char flag[N];10 memset(flag,‘0‘,N);11 flag[0]=‘1‘;12 flag[1]=‘1‘;13 14 for(i=2;i<=sqrt(N);i++){15 if(flag[i]==‘0‘){16 for(j=i*i;j<N;j+=i){17 flag[j]=‘1‘;18 }19 }20 }21 22 int number;23 24 while(1){25 scanf("%d",&number);26 27 if(number==0)28 break;29 30 for(i=2;i<=number;i++){31 if(flag[i]==‘0‘)32 printf("%d ",i);33 }34 35 printf("\n");36 }37 38 return 0;39 }
素数筛子算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。