【C语言】–判断101 – 200之间有多少个素数，并输出所有素数。

目录

方法一：直接粗暴法

方法二：奇数法

方法三：平方根法

题目：判断101 – 200之间有多少个素数，并输出所有素数。

素数（质数）：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数。

方法一：直接粗暴法

判断一个数x是不是素数，只需要从2开始到x-1结束做取余运算，余数为零则表示它能被其中一个整数整除，即不是素数。这种方法最简单直接，但是运算量也是最大的。

#includeint main(){int i,j,m=0,flag=1;for (i = 101;i < 201;i++){for (j = 2;j < i;j++){if (i % j == 0)//如果余数是零则表示不是素数{flag = 0;break;}}if (j==i)//从2到i-1取余操作的余数都不是0，则是素数{m++; //素数个数加一printf(" %d ", i);//把这个素数输出if (m % 5 == 0)//每五个素数一行printf("\n");}}printf("\n一共有%d个素数\n", m);return 0;}

方法二：奇数法

顾名思义，2的倍数肯定都不是素数，所以，为了减少运算量我们改变两层循环中的递增值。第一层循环从101开始，每次递增2，即101，103，105···199；第二层循环从3开始，同样也每次递增2，即3，5，7···x-1。

#includeint main(){int i, j, m = 0, flag = 1;for (i = 101;i < 201;i+=2){for (j = 3;j < i;j+=2){if (i % j == 0)//如果余数是零则表示不是素数{flag = 0;break;}}if (j == i)//从2到i-1取余操作的余数都不是0，则是素数{m++; //个数加一printf(" %d ", i);//把这个素数输出if (m % 5 == 0)//每五个一行printf("\n");}}printf("\n一共有%d个素数\n", m);return 0;}

方法三：平方根法

如果一个整数x为素数，那么就不能写成两个数相乘等于x的形式，即x = a * b。所以，如果整数x无法被小于等于x的平方根的数整除，则x为质数，即在第二层循环只需要递增到x的平方根就可以了。

#include#includeint main(){int i, j, k, m = 0;for (i = 101;i < 201;i+=2){k = sqrt(i);//平方根for (j = 2;j k) {m++;printf(" %d ", i);if (m % 5 == 0)printf("\n");}}printf("\n一共有%d个素数\n", m);return 0;}

运行结果

总结

方法三是运算次数最少的算法。对素数的特点进行分析，一步一步地对代码进行改良，减少运算次数，得到相对简单的方法。