实现C语言打印1-100之间的素数
定义：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
方法一 试除法
依次遍历 挑选出符合条件的数字打印
1.创建一个嵌套循环，实现遍历
int i = 0, j = 0; for (i = 2; i <= 100; i++) { for (j = 2; j <= i; j++) { } }
2.设定条件
if (i % j == 0)//如果被数整除就结束本次循环 { break; } if (i == j)//结束内层循环后 判断i 是否相等 相等证明是素数 { printf("%d ",i); }
完整代码实现
#include <stdio.h> int main() { int i = 0, j = 0; for (i = 2; i <= 100; i++) { for (j = 2; j <= i; j++) { if (i % j == 0) { break; } } if (i == j) { printf("%d ",i); } } return 0; }
去偶数法
已知在1-100之内偶数永远不可能是素数 所以每次i可以跳过偶数
1.如上创建嵌套循环 不过此处进行一个小优化 把判断条件使用一个flag数进行判断
int i = 0,j = 0; printf("2 "); for (i = 3; i <= 100; i += 2) { int flag = 1;//注意 需要把flag放在外层循环内 因为如果非素数的话会导致flag为0 需要每次进行重置 for (j = 2; j < i; j++) { } }
2.符合条件进行打印 需要注意的是直接去除偶数的话 会缺少了一个2 需要补上
if (i % j == 0) { flag = 0;//在内层循环中 j要小于i 不能等于 否则i%j==0 flag恒为0 break; } if (flag == 1) { printf("%d ",i); }
完整代码实现
#include <stdio.h> int main() { int i = 0,j = 0; printf("2 "); for (i = 3; i <= 100; i += 2) { int flag = 1; for (j = 2; j < i; j++) { if (i % j == 0) { flag = 0; break; } } if (flag == 1) { printf("%d ",i); } } return 0; }
sqrt()函数法
在sqrt开方下会产生两个数 一个数如果为非素数的话 那么它肯定依然可以取模。这样子循环只要一半 提高了效率。
#include <stdio.h> #include <math.h> int main() { int flag = 0; for (int i = 2; i <= 100; i++) { flag = 1; for (int j = 2; j <= sqrt(i); j++) { if (i % j == 0) { flag = 0; break; } } if (flag == 1) { printf("%d ",i); } } return 0; }
