相信学习C语言的小伙伴们，一定都遇到过用C语言去判断素数的题目。
今天和大家分享一些素数的判断方法，希望能够给刚入门的小伙伴们提供清晰的思路，废话不多说，开整。
举例：请列举出100~200之间的素数
1
什么是素数？
素数——只能被1和本身整除的数字（除了数字1）
2
如何判断这些素数？
假设 i 是我们要判断的数字
- 试除法——每拿到一个数的时候，如果 i 能被 2 ~ i-1 之间任一整数整除，可以说明是素数；
- 每拿到一个数据，只需要检测其：[2, i/2]区间内是否有元素可以被2i整除即可，可以说明i不是素数；
- 如果i能够被[2, sqrt(i)]之间的任意数据整除，则i不是素数——如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于 sqrt(m)；
方法一：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
int i, j, count = 0;
for (i = 100; i <= 200; i++)//外层循环让其产生100~200之间的所有数字
{
//判断素数
for (j = 2; j < i; j++)//试除阶段
{
if (i % j == 0)
break;
}
// 上述循环结束之后，如果j和i相等，说明[2, i）之间的所有数据都不能被i整除，则i为素数
if (j == i)
{
count++;//记录素数的个数
printf("%d ", i);
}
}
printf("\ncount=%d\n", count);
return 0;
}上述方法虽然可行，但是我们不难发现，超过 i 一半的数据，不是 i 的倍数，进行了多次无效的循环试除；接下来看看优化后的代码二；
方法二：
既然多次无效的试除，我们可以将试除数据减少一半；只要拿到一个数字在试除的过程中，只要被[2, i/2]区间整除，就一定不是素数；
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
int i, j, count = 0;
for (i = 100; i <= 200; i++)//外层循环让其产生100~200之间的所有数字
{
//判断素数
for (j = 2; j <= i / 2; j++)
{
if (i % j == 0)
break;
}
if (j > i / 2)
{
count++;
printf("%d ", i);
}
}
printf("\ncount = %d\n", count);
return 0;
}方法二确实是比方法一减少循环试除的次数，但是细心一点还是会发现，当减少一半试除数据时，还是存在少部分没用的数据；再次优化，看代码三
方法三：
如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于sqrt(m)，另一个大于或等于 sqrt(m)；
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
int main()
{
int i, j;
int count = 0;
for (i = 100; i <= 200; i++)//外层循环让其产生100~200之间的所有数字
{
//判断素数
for (j = 2; j <= sqrt(i); j++)
{
if (i % j == 0)
break;
}
if (j > sqrt(i))
{
count++;
printf("%d ", i);
}
}
printf("\ncount = %d\n", count);
return 0;
}方法四：
继续对方法三优化，只要i不被[2, sqrt(i)]之间的任何数据整除，则i是素数，但是实际在操作时i不用从100逐渐递增到200，
因为出了2和3之外，不会有两个连续相邻的数据同时为素数
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <math.h>
int main()
{
int i, j;
int count = 0;
for (i = 101; i <= 200; i += 2)//偶数不可能是素数
{
//判断素数
for (j = 2; j <= sqrt(i); j++)
{
if (i % j == 0)
{
break;
}
}
if (j > sqrt(i))
{
count++;
printf("%d ", i);
}
}
printf("\ncount = %d\n", count);
return 0;
}素数的求解有多种方法，这里我们只简单地介绍两种算法，以及优化；如果大家有兴趣，我给大家推荐一篇文章叫《素数求解的n种境界》，大家可以下去自己去好好研究一下；拓宽自己的思路。
总结一些小经验：编写代码现以实现为主，在此基础上去培养优化代码的思想，在以后的学习或者面试中会有很好的效果。