目录
1.题目解析
2.代码
3.优化
【代码】
4.再进一步优化
【代码】
1.题目解析
- 首先要产生100~200之间的数字
- 然后判断每个数字是否是素数
如何判断一个数字是否是素数？
素数只能被1和它本身整除，那么我们就可以用 2~i-1 之间的每个数去试除 i，如果 2~i-1 之间有任何一个数字能整除 i，那么 i 就不是素数，如果 2~i-1 之间任意一个数字都不能整除 i，那么 i 就是素数。
2.代码
注意：flag 这个变量只能在第一层 for 循环开始时创建，用来标记 for 循环一开始时产生的100~200的每个数字是否为素数，不能在第一层for循环外面创建，否则代码错误。
#include<stdio.h>int main()
{int i = 0;int count = 0;//首先产生100~200之间的数字for (i = 100; i <= 200; i++){int flag = 1;//假设i是素数//再用2~i-1之间的数字去试除iint j = 0;for (j = 2; j <= i - 1; j++){if (i % j == 0){flag = 0;//i被j整除，即表示i不为素数，标记flag变为0break;//跳出的是内部for这层循环}}if (flag == 1){//flag仍为1，说明i是素数printf("%d ", i);count++;}}//count 用来计算100~200之间有多少个素数printf("\ncount=%d\n", count);return 0;
}3.优化
【代码】
思考这代码能不能进一步优化？
从源头开始想，从产生100~200的数字时，偶数不可能为素数，所以就无需判断偶数是否为素数，那就干脆不产生偶数
#include<stdio.h>int main()
{int i = 0;int count = 0;//调整：产生100~200之间的奇数数字for (i = 101; i < 200; i+=2){int flag = 1;//再用2~i-1之间的数字去试除iint j = 0;for (j = 2; j <= i - 1; j++){if (i % j == 0){flag = 0;break;//跳出的是内部for这层循环}}if (flag == 1){printf("%d ", i);count++;}}printf("\ncount=%d\n", count);return 0;
}4.再进一步优化
若 c=a*b，那么 a 和 b 其一一定小于 c 的算术平方根。那么我们在找试除 i 的值时就只需找 2~sqrt(i) 之间的值即可，sqrt(i) 是求 i 的平方根的，包含头文件 math.h 。
【代码】
#include<stdio.h>
#include<math.h>int main()
{int i = 0;int count = 0;//首先产生100~200之间的数字for (i = 101; i < 200; i+=2){int flag = 1;//再用2~sqrt(i)之间的数字去试除iint j = 0;for (j = 2; j <= sqrt(i); j++){if (i % j == 0){flag = 0;break;//跳出的是内部for这层循环}}if (flag == 1){printf("%d ", i);count++;}}printf("\ncount=%d\n", count);return 0;
}通过两次优化，提高了代码的效率！
本题讲解到此结束，再见~
云边有个稻草人
期待与你的下一次相遇
