这是一篇关于素数的介绍，以及介绍判断是否为素数的一篇博客，我会将方法一一列举出来方便大家理解和观看。
🍊
前言🍊
我们在C语言的学习中会遇到各种各样的数学问题，每次遇到这些数学问题时，我们一定要学习如何用代码的方法表示出来，加深理解，并且强化自己的能力，今天我们来看看素数
什么是素数🍊
质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数（质数）整除，换句话说就是该数除了1和它本身以外不再有其他的因数。或者更简单一点素数的定义：只能被常数1或自己整除，不能被其他整数整除的正整数。
eg：如9 =1 * 9= 3 * 3 ，所以9不是素数
4=2*2，4可以写成比4小的数相乘，因此4不是素数。
2，比2小的自然数有0和1，它们无论怎么相乘，得不到2，所以2是素数。
3，比3小的自然数有0,1,2，它们无论怎么相乘，得不到3，所以3是素数。
5，比5小的自然数有0,1,2,3,4，它们无论怎么相乘，得不到5，所以5是素数。
| 接下来我们就要开始介绍方法了 |
试除法🍊
暴力穷举法（2 - (i-1)）：🍊
我们先来看看流程图
这是我们最基础的一种方法，虽然它的效率不是很高但是，我们后面的优化都是基于这个方法，所以要好好理解.
解释：假设i是我们要判断的数，我们就利用2 ~ i-1去模（%），如果 i % j (2~i-1)==0 ，就说明有一个数能够整除i，那么i就不符合素数的定义，就不是素数。
我们来看代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int i = 0; scanf("%d", &i); int j = 0; for (j = 2; j < i; j++) { if (i % j == 0) { printf("%d不是素数\n", i); break; } } if (1 == i) { printf("1不是素数，请不要再输入"); } if (i == j ) { printf("%d是素数\n", i); } return 0; }
我们也还是讲解一下代码的思路，首先，借助for循环测出是否有能够整除的数，如果有就break；如果是素数那么for循环的print就不会执行，但是最后j还是会++一下,即使已经不符合for循环的第二个判断条件，所以跳出for循环的就是素数，当然还有一个数要排除，就是不能输入1，因为1不是素数.
| 为了与后续的优化进行对比我们改变一下代码,让大家对效率有一个明显的理解。我们就从2-150开始进行测试效率 来看代码 |
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int i = 0; int count1 = 0;//用以统计素数的个数 int count2 = 0;//用以计算要试除多少次 for (i = 2; i <= 150; i++) { int j = 0; for (j = 2; j < i; j++) { count2++; if (i % j == 0) { break; } } if (i == j) { printf("%d是素数 ", i); count1++; } } printf("\n素数的个数为%d", count1); printf("\n试除的次数为%d", count2); return 0; }
我们现在在2~150中找出了35个素数，但是一看要试除的次数，居然要2414次，其实我们仔细想一想就知道这是正常的，我们现在就可以进行优化了
境界+1（2 - i/2）🍊
在上面的方法中我们是依靠2 -（i-1）去试除，但是实际上我们可以直接用
2 ~ i / 2去试除这是为什么呢？
我们知道16 是可以由 两个因子相乘得到，比如 2 * 8 ，实际上这两个因子必定有一个因子是小于等于要判断数的二分之一，16/2 =8 也就是说我们只要判断2~8就行。只要2 ~8中有一个数能被16整除就说明16不是素数。
>接下来看看这个方法能优化多少？
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int i = 0; int count1 = 0;//用以统计素数的个数 int count2 = 0;//用以计算要试除多少次 for (i = 2; i <= 150; i++) { int j = 0; for (j = 2; j <=i/2; j++) { count2++; if (i % j == 0) { break; } } if ( j > i/2 ) { printf("%d是素数 ", i); count1++; } } printf("\n素数的个数为%d", count1); printf("\n试除的次数为%d", count2); return 0; }
大家注意一下，这里最后面if的 判断条件，一定是要j>i/2才行，因为当2~i/2没有一个数能被整除时，j最后还是会++一下，最终大于i/2
看看能优化多少？
我们看到试除的次数是1294，而我们第一种方法是2414，可以说我们这个方法已经优化了一半了。接下来我们再来进行下一次优化！
境界再+1（去偶数）🍊
我们现在在研究2~150的素数判断优化过程，而实际在在2 ~150中还有很多偶数本身就可以去除，这也是一步很简单的优化，离我们最后的优化更近一步。也有人称去除有关2的合数，就是说去除有可以有2作为因子的数。
来看代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int main() { int i = 0; int count1 = 0;//用以统计素数的个数 int count2 = 0;//用以计算要试除多少次 printf("2是素数 "); for (i = 3; i <= 150; i+=2) { int j = 0; for (j = 2; j <=i/2; j++) { count2++; if (i % j == 0) { break; } } if ( j > i/2 ) { printf("%d是素数 ", i); count1++; } } printf("\n素数的个数为%d", count1); printf("\n试除的次数为%d", count2); return 0; }
我们实际上只需要改变一下最外层的for循环，当然我们还不能漏掉2这个素数。
本来这个方法我应该放在更前面的，因为现在看起来去合数这个方法并没有增加多少效率。但是放在前面的话效果就会明显些。好，我们现在看结果与我们上一个方法对比我们去合数的方法只是从1294变成1220
虽然不明显但是还是能算得上优化。
