❗ 素数 ❕
素数(质数)：只能被1和它本身整除的数。 注：1不是素数
🔑 如果是素数就要不断的去试除来证明，直到全部排除🔑
#include<stdio.h> int main() { int i = 0; int j = 0; for(i = 100; i <= 200; i++) { //判断i是否为素数 //试除区间：2->i-1 for(j = 2; j < i; j++)//这里就排除了1和素数本身 { if (i % j == 0) break; if (i % j != 0 && j == i - 1) printf("%d ", i); } } return 0; }
🔑 优化：相反不是素数则有一个数满足条件 (能被除了1和它本身的数整除) ，它就不是素数 🔑
#include<stdio.h> int main() { int i = 0; int j = 0; for(i = 100; i <= 200; i++) { for(j = 2; j < i; j++) { //非素数，直接break if (i % j == 0) break; } //这里说明i已经将所有的数试除了，所以这个数是素数 if (i == j) printf("%d ", i); } return 0; }
🔑 使用 flag 标志。这是另一种方法 - 每道题都可能有不同的解决方法，多思考从各个角度解决问题 🔑
#include<stdio.h> int main() { int i = 0; int j = 0; for(i = 100; i <= 200; i++) { int flag = 1;//给1个标记 for(j = 2; j < i; j++) { if (i % j == 0) { flag = 0;//如果是素数则将标记赋值为0 break; } } if (1 == flag)//1是素数，0不是素数 printf("%d ", i); } return 0; }
🔑
优化思路：减少试除的次数
m = a * b
a 和 b中至少有一个数字是 <= 开平方 m 的；如果在开平方 m 之前找到 1 个因子能够整除 m 的话，那就可以不用找另 1 个因子了
16 = 2 * 8 = 4 * 4
也就是说如果能找到 2 能够整除 16 的话，就没必要去找 8 能不能整除 16 了
在之前是使用i去试除 2 -> i - 1 之间的数；现在是试除 2 -> sqrt(i) 之间的数
🔑
#include<stdio.h> #include<math.h> int main() { int i = 0; int j = 0; for (i = 100; i <= 200; i++) { int flag = 1; for (j = 2; j <= sqrt(i); j++)//sqrt是开平方函数，所在头math { if (i % j == 0) { flag = 0; break; } } if (1 == flag) printf("%d ", i); } return 0; }
🔑 再优化：偶数有可能是素数吗? - 当然是不可能的 🔑
#include<stdio.h> #include<math.h> int main() { int i = 0; int j = 0; for (i = 101; i <= 200; i+=2)//101、103、105、107...(从源头上跳过偶数) { int flag = 1; for (j = 2; j <= sqrt(i); j++)//sqrt是开平方函数，所在头math { if (i % j == 0) { flag = 0; break; } } if (1 == flag) printf("%d ", i); } return 0; }
🔑 再优化 。。。 。。。额，学废了学废了。。。。当然大家如果还有别的方法 ，希望能分享出来一起学习 🔑
//欢迎大佬补充 //欢迎大佬补充
输出结果
