C语言——打印100~200之间的素数的三种方法

题目：打印100~200之间的素数

首先要知道什么是素数

素数是指只能够被1或其本身整除

方法一： 利用flag标志i是否为素数，若为素数则flag为1，否则则为0

代码实现如下：

#include int main(){int i = 0;int j = 0;int count = 0;for (i = 101; i <= 200; i++){int flag = 1;//假设i是素数//生成100-200之间的数//每次循环进来一个i，用2~i-1之间的数试除i，以此判断i是不是素数for (j = 2; j <= i-1; j++){if (i % j == 0){flag = 0;//表示i不是素数break;//当i~i-1之间有任意数满足这个条件，就利用break跳出循环}}if (flag == 1){printf("%d ", i);count++;//计算一共多少素数}}printf("\ncount = %d\n", count);return 0;}

方法一 的优化：由于素数不可能是偶数，所以可以修改for循环调整部分的代码

相较于方法一，减少了部分数的计算，提高效率

#include int main(){int i = 0;int j = 0;int count = 0;for (i = 101; i <= 200; i+=2){int flag = 1;//假设i是素数//生成100-200之间的数//每次循环进来一个i，用2~i-1之间的数试除i，以此判断i是不是素数for (j = 2; j <= i - 1; j++){if (i % j == 0){flag = 0;//表示i不是素数break;//当i~i-1之间有任意数满足这个条件，就利用break跳出循环}}if (flag == 1){printf("%d ", i);count++;//计算一共多少素数}}printf("\ncount = %d\n", count);return 0;}

方法二：利用sqrt函数进一步优化

举例：判断一个数n是否为素数

若 n == 16 16可以写成16 = 4 * 4 或 16 = 2 * 8 即n == a * b

说明至少有一个因子是小于等于√n，所以可以省略之后的判断

代码实现如下：

#include  #include //由于使用了sqrt()函数，所以需要引用math.h的头文件int main(){int i = 0;int j = 0;int count = 0;for (i = 101; i <= 200; i += 2){int flag = 1;//假设i是素数//生成100-200之间的数//每次循环进来一个i，用2~i-1之间的数试除i，以此判断i是不是素数for (j = 2; j <= sqrt(i); j++){if (i % j == 0){flag = 0;//表示i不是素数break;//当i~i-1之间有任意数满足这个条件，就利用break跳出循环}}if (flag == 1){printf("%d ", i);count++;//计算一共多少素数}}printf("\ncount = %d\n", count);return 0;}