质数是指在大于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;}
总结:四种方法大体思路都是相同的,即根据质数概念来进行判断,不过判断范围不断缩小,计算量不断减小,代码执行效率越来越高了
希望可以帮助到你,有问题欢迎交流指正!