题解原理:
从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语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:655 |
妹子杀手的故事 (C语言代码)浏览:679 |
P1002 (C语言代码)浏览:970 |
淘淘的名单 (C语言代码)答案错误???浏览:593 |
输出正反三角形 (C语言代码)格式错误!!!浏览:1140 |
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:672 |
IP判断 (C语言描述,蓝桥杯)浏览:1094 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:586 |
1642题解浏览:708 |
1113题解浏览:784 |