【C语言】判断一个数是否为素数（素数求解的N种境界）

这是一篇关于素数的介绍，以及介绍判断是否为素数的一篇博客，我会将方法一一列举出来方便大家理解和观看。

目录

• 前言
• 什么是素数
• 试除法
• • 暴力穷举法（2 – (i-1)）：
  • 境界+1（2 – i/2）
  • 境界再+1（去偶数）
  • 境界再再+1 sqrt（i）
• 筛选法
• 筛选法优化
• 总结

前言

我们在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#includeint 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不是素数.

#define_CRT_SECURE_NO_WARNINGS 1#includeint 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#includeint 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#includeint 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
虽然不明显但是还是能算得上优化。

境界再再+1 sqrt（i）

实际上这个才是我们最应该掌握的方法，我们来看看如何优化。

>我们现在是从2~ √i 去试除，
举个例子如果一个数不是素数那么它一定是可以进行分解的，
分解成两个因子相乘的情况，
我们看上面12的因子，这么多因子实际上我们只需要判断√12前面的就行，
为什么呢？
如果√12前面没有一个因子能被整除，那么后面（√12后面）就没有一个因子能够被整除，
因为因子都是要相乘的，比如2和6，我都已经判断2能够被整除，那我还需要判断后面的6吗？如果不是很肯定对不对就多试试多分解几组。
我们来看代码吧。

#define_CRT_SECURE_NO_WARNINGS 1#include#includeint 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 <=sqrt(i); j++){count2++;if (i % j == 0){break;}}if ( j > sqrt(i) ){printf("%d是素数 ", i);count1++;}}printf("\n素数的个数为%d", count1);printf("\n试除的次数为%d", count2);return 0;}

这个代码需要在第二个for循环改变第二个判断条件，让jsqrt (i) ,因为已经解释很多次这里我就不解释了。我们来看效率

我们最后试除的次数变成仅仅只要343了，还记得我们最开始有多少吗？我记得是2414，现在我们感受到优化的快乐了吗？

总得来说试除法的思路都差不多。还是比较好理解的。我们来看看另一种方法也是我们真正能够与别人方法不一样的一种，希望大家能够掌握。

筛选法

我们筛选法还有一个名字叫，埃拉托斯特尼算法。这个名字念起来非常拗口，这是一个古希腊的名字。此人是个古希腊的大牛，是大名鼎鼎的阿基米德的好友。他虽然没有阿基米德那么出名，但是也非常非常厉害，在数学、天文学、地理学、文学、历史学等多个领域都有建树。并且还自创方法测量了地球直径、地月距离、地日距离以及黄赤交角等诸多数值。要知道他生活的年代是两千五百多年前，那时候中国还是春秋战国时期，可以想见此人有多厉害。

思路

埃式筛法的思路非常简单，就是用已经筛选出来的素数去过滤所有能够被它整除的数。这些素数就像是筛子一样去过滤自然数，最后被筛剩下的数自然就是不能被前面素数整除的数，根据素数的定义，这些剩下的数也是素数。

如果还不懂我就来解释一下，假如我们要筛选出120以内所以的素数，那我们就可以从2这个第一个素数开始，我们把因子中含有2的，也就是偶数全部筛选掉，简单理解就是去掉。然后我们从2的下一个素数开始，2的下一个素数是3，那么我们就把因子中有3的全部筛选掉，3的下一个素数又是谁？是5，然后我们再重复上面的过程，5 之后的素数是7，然后再再循环上面的过程。当7的循环结束之后我们就可以去找还有哪些数没有被筛掉，没有被筛掉的数就是素数。

给大家一个经典的gif加强理解

接下来我们看代码

#define_CRT_SECURE_NO_WARNINGS 1#include#includeint main(){int i = 0;int count1 = 0;//用以统计素数的个数int count2 = 0;//用以计算要筛掉多少次int arr[151] = { 0 };//创建数组for (i = 2; i <= 150; i++)//初始化{arr[i] = 1;}for (i = 2; i <= 150; i++)//用下标代表数字{if (arr[i]) //是1才进入if{int j = 0;printf("%d ", i);//打印素数count1++;for (j = i+i; j <= 150; j += i)//把素数的倍数都赋为0；{//让下一个进入if的必定是素数{ arr[j] = 0;count2++; //}}}printf("\n素数的个数为%d", count1);printf("\n试除的次数为%d", count2);return 0;}

*简单说一下代码思路，我是建立一个数组，
把应该筛掉的数全部变为0，
让被筛掉的那些数作为数组的下标。
比如我从2开始筛，2之后的偶数就无法打印，然后就是3，然后就是5，然后就是7，然后就是11。*大家知道为什么这里要筛11吗？因为我们要筛的最大值为150，而√150的值是12.2。12.2是大于11的所以我们这次要多筛11（这里我不是很确定，大家看看就好，影响不大）

让大家看看筛选法的效率是多么的惊人。

234次就直接能够把2 ~150 的素数全部筛选完。

筛选法优化

我们讲解一下优化的思路，
其实我上面筛选法的代码还是可以优化的，
为什么呢？
在最后我们是把有关的倍数数组全部赋值为0，
>但是假如这个数是12呢？
12我们在以2为筛选倍数的时候赋为0，
但是在以3位筛选倍数的时候又赋值为0。
这样就重复了。大家能明白我的意思吗
？如果不明白大家可以再看看那个gif相信大家可以发现这个道理。
埃拉托斯特尼也注意到过这一点。

当 i=2 时，我们只需从 2 * 2 = 4 开始筛2的倍数；当 i=3 时，其实我们只需从3 * 3 = 9开始筛3的倍数 当 i = 5 时，我们应该从25开始筛。

for (j = i+i; j <= 150; j += i)

当i = 3时，优化前的代码我们是从6开始筛，但是6其实已经被作为2的倍数筛过一次，而3+3+3，也就是9还没有被筛。
当i = 5时，优化前的代码我们是从10开始筛，但是10也被作为2的倍数筛走，那15呢？对是的，被作为3的倍数筛走，那么20？ 也不行只有25才行。
那么我们就发现了规律，我们应该从该素数的平方开始筛。

最后再来看代码

#define_CRT_SECURE_NO_WARNINGS 1#include#includeint main(){int i = 0;int count1 = 0;//用以统计素数的个数int count2 = 0;//用以计算要筛掉多少次int arr[151] = { 0 };//创建数组for (i = 2; i <= 150; i++)//初始化{arr[i] = 1;}for (i = 2; i <= 150; i++)//用下标代表数字{if (arr[i]) //是1才进入if{int j = 0;printf("%d ", i);//打印素数count1++;for (j = i*i; j <= 150; j += i)//把素数的倍数都赋为0；{//让下一个进入if的必定是素数{ arr[j] = 0;count2++; //}}}printf("\n素数的个数为%d", count1);printf("\n试除的次数为%d", count2);return 0;}

最后也是最激动人心的时刻，咱们来看看效率

芜湖！！！166！！！，看到这里的你被埃式筛法震惊了吗？说真的我被震惊了。

总结

首先很感谢能看到这里的小伙伴，真的很感谢有人能看我的博客，说真的我在写这篇博客的时候真的很用心，我要感谢链接: 圣喵学长的博客，以及一些知乎上面的大佬的文章提供给我的参考。

通过这篇博客希望大家能够明白算法的奥秘，如果有兴趣的同学可以去知乎上寻找更有难度的方法如欧拉筛等等。这篇博客到这里就结束了。

各位看官姥爷如果这篇博客有帮助到你，麻烦你动动小手点点赞吧，只需要一个赞就能让我高兴很久，^ _ ^.如果有任何错误有麻烦在评论区指出。