C语言求质数（素数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

下面我们以输出100 – 200间所有质数为例来讲述求质数的几种方法

方法一：遍历法

该方法思想就是用该数字n除 2 到 n-1 的所有数字，如果余数都不为零，说明n为质数

#define _CRT_SECURE_NO_WARNINGS 1#include //打印100-200之间的素数int main() {int i = 0, flag = 0, j = 0, count = 0;for (i = 100; i <= 200; i++) {//外层循环，用于生成100-200这一百个数字flag = 1;for (j = 2; j <= i-1; j++) {//内层循环，用于判断每一个i是否为质数if (i % j == 0) {flag = 0;//flag=0,即i不是质数break;//break函数跳出当前循环体；}}if (1 == flag) {printf("%d ", i);count++;//用来计数（质数个数）}}printf("\ncount = %d", count);return 0;}

方法二：对半找

方法一思路简单，但效率太低，有很多可以优化的地方

超过 i/2 的数肯定不是 i 的倍数，因此我们可以将内层循环的范围缩小一半，减少无意义的运算

#define _CRT_SECURE_NO_WARNINGS 1#include //打印100-200之间的素数int main() {int i = 0, flag = 0, j = 0, count = 0;for (i = 100; i <= 200; i++) {//外层循环，用于生成100-200这一百个数字flag = 1;for (j = 2; j <= i/2; j++) {//内层循环，用于判断每一个i是否为质数if (i % j == 0) {flag = 0;//flag=0,即i不是质数break;//break函数跳出当前循环体；}}if (1 == flag) {printf("%d ", i);count++;//用来计数（质数个数）}}printf("\ncount = %d", count);return 0;}

方法三：

我们继续在方法二的基础上进行优化，这次把目光放到外层循环上

一个很简单的事实，偶数一定不是质数，所以我们只用对100-200间奇数进行判断即可

#define _CRT_SECURE_NO_WARNINGS 1#include int main() {int i = 0, flag = 0, j = 0, count = 0;for (i = 101; i <= 200; i+=2) //偶数不是素数{flag = 1;for (j = 2; j <= i/2; j++) {if (i % j == 0) {flag = 0;break;}}if (1 == flag){printf("%d ", i);count++;}}printf("\ncount = %d", count);return 0;}

方法四：

保留前三种方法的优点，我们继续对代码进行优化

i如果可以表示成两因数相乘的形式，那么其中一个因数一定满足小于等于根号下i，知道这点后，我们可以进一步缩小内层循环的判断范围

这里我们开平方用到sqrt()函数，需要引用其头文件math.h sqrt – C++ Reference

#define _CRT_SECURE_NO_WARNINGS 1#include #includeint main() {int i = 0, flag = 0, j = 0, count = 0;for (i = 101; i <= 200; i += 2) {flag = 1;for (j = 2; j <= sqrt(i); j++) {if (i % j == 0) {flag = 0;break;}}if (1 == flag){printf("%d ", i);count++;}}printf("\ncount = %d", count);return 0;}

总结：四种方法大体思路都是相同的，即根据质数概念来进行判断，不过判断范围不断缩小，计算量不断减小，代码执行效率越来越高了

希望可以帮助到你，有问题欢迎交流指正！