目录
1.什么是素数：
素数又叫质数，只能被1和它本身整除
例如：7，只能被1和7整除，
1，2，3，4，5，6都不能整除7
所以7是素数
2.题目的分析与思路
分析题目，要想打印100~200之间的素数，首先需要会打印100~200之间的数
- 打印100~200之间的数：
#include<stdio.h> int main() { int i = 0; for (i =100; i <= 200; i++) printf("%d ", i); return 0; }
关于for循环可以参阅另一篇博客 分支和循环语句
执行结果如下：
接下来需要判断i是否为素数
- 判断i是否为素数：
那么该如何判断呢？
可以使用 2 到 i-1 之间的数去试除 i，如果2 到 i-1 之间没有数能整除 i ，那么i就是素数
例如：前面我们说 7是素数
那么我们用2到6之间的数试除7，如果没有数能整除7那么7就是素数
综上，我们需要先产生2到 i-1 之间的数
- 2到 i-1之间数的产生：
#include<stdio.h> int main() { int i = 0; for (i = 100; i <= 200; i++) { //下面是2到 i-1之间数的产生 int j = 0; for (j = 2; j < i; j++) { //这里需要用j试除i } } printf("%d ", i); return 0; }
如上，接下来我们需要用 j 试除 i
- 最终代码：
#include<stdio.h> int main() { int i = 0; for (i = 100; i <= 200; i++) { int flag = 1;//表示是素数 //判断i是否为素数 //使用2~i-1之间的数字去试除i int j = 0; for (j = 2; j < i; j++) { if (i % j == 0) //表示不是素数 { flag = 0; break; //结束当前循环的周期，执行下面的语句，注意if语句不是循环 } } if (flag == 1) printf("%d ", i); } return 0; }
实际上，上述方法比较复杂，接下来我们来介绍一种效率更高
3.第二种思路：
如果 i=m*n，那么一定可以在2 ~ i的开平方 之间找到一个 i 的因子
比如：
16=2*8
16=4*4
那么
如果在 2~i 的开平方之间可以找到一个因子，后面（i 的开平方~i之间）必然也有一个因子。
如果在 2~i 的开平方之间没有找到一个因子，后面必然也没有因子。
#include<stdio.h> #include<math.h> int main() { int i = 0; int count = 0; for (i = 100; i <= 200; i++) { int flag = 1;//表示是素数 //判断i是否为素数 //使用2~i-1之间的数字去试除i int j = 0; for (j = 2; j <=sqrt(i); j++) { //拿j来试除i if (i % j == 0) { flag = 0; break; } } if (1 == flag) { count++; printf("%d ", i); } } printf("\ncount = %d\n", count); return 0; }
4.再次优化
100~200之间的偶数不可能为素数所以进行如下优化
编辑
计算输出的个数：
代码如下：
#include<stdio.h> int main() { int i = 0; int count = 0; for (i = 100; i <= 200; i++) { int flag = 1;//表示是素数 //判断i是否为素数 //使用2~i-1之间的数字去试除i int j = 0; for (j = 2; j < i; j++) { //拿j来试除i if (i % j == 0) { flag = 0; break; } } if (1 == flag) { count++; printf("%d ", i); } } printf("\ncount = %d\n", count); return 0; }
后面输出个数的方法与之类似，这里就不展示了
