题解原理:
从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。
注意事项:
①利用数组的下标作为1-n个数,其值用来标记
②当类推筛选到第根号n时已经筛选完成,不必筛选到筛子为空。
参考代码:
#include<stdio.h> #include<string.h> //memset函数 #include<math.h> //sqrt()求平方根 #define N 10001 //假定N最大值为10000 int a[N]; int main() { int n; scanf("%d", &n); memset(a, 0, sizeof(a)); //①初始默认都为素数置为0,不是素数标记1,下面再筛去。 int i = 1; a[1] = 1; //1不是素数、将其置1 for (i = 2; i < sqrt(n); i++) //i为素数因子,②当i等于根号n时,可筛去所有的非素数。 { if (a[i] == 0) {//i未标记,则i是素数. int j; for (j = 2; j * i <= n; j++) {//将i的倍数标记 a[j*i] = 1; } } }//已将a[1]-a[n]标记完成。 for (i = 1; i <= n; i++) { //输出 if (!a[i]) printf("%d\n", i); } return 0; }
0.0分
1 人评分
C二级辅导-阶乘数列 (C语言代码)浏览:833 |
C语言程序设计教程(第三版)课后习题6.11 (C++代码)(有个库函数叫sqrt)浏览:866 |
上车人数 (C语言代码)浏览:1180 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:688 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
【排队买票】 (C语言代码)浏览:900 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:473 |
图形输出 (C语言代码)浏览:1387 |
【偶数求和】 (C语言代码)浏览:431 |
数组输出 (C语言代码)浏览:703 |