目录
1、什么是素数
方法1、基础求解（逐个试除）
算法优化
方法2、利用平方根求解
总结
提示：关于for循环
1、什么是素数
求素数，首先我们要知道什么是素数，这是我在百度百科上找的关于素数的定义。素数就是只能被1和自身整除的正整数。
2、C语言实现找素数
我们已经知道什么是素数了，那接下里我们就用C语言来实现，判断一个数是不是素数。
我们以100~200为例子。
方法1、基础求解（逐个试除）
试除法就是把在该数之前的数都拿来除一遍，如过有余数为0，则不是素数。
代码及运行结果如下：
#include<stdio.h>
int main()
{
int a = 200;
int i = 0;
int j = 0;
int count = 0;
//100~200遍历
for (i = 2; i <= a; i++)
{
//设置标记
int flag = 1;
//逐个试除
for (j = 2; j < i; j++)
{
if (i % j == 0)
{
//余数为0，标记改变
flag = 0;
break;
}
}
//if语句非0为真，查看标记是否改变
if (flag)
{
//统计个数
count++;
//打印素数
printf("%d ", i);
}
}
printf("\n总共有%d个", count);
return 0;
}
算法优化
我们知道，除了2这个数，其他素数都是奇数，那我们就用判断奇数就行（如果计算包含2，记得把2带上）。
另外算到该数的1/2的时候就能判断出该数不是素数，那就没必要往后再算。
优化代码及运行结果如下：
#include<stdio.h>
int main()
{
int a = 200;
int i = 0;
int j = 0;
int count = 0;
//从101开始，每次自增2，遍历奇数
for (i = 101; i <= a; i+=2)
{
for (j = 2; j < i; j++)
{
if (i % j == 0)
{
//余数为0跳出循环
break;
}
//大于或等于该数的1/2则为质数
if (j >= i / 2)
{
count++;
printf("%d ", i);
break;
}
}
}
//打印个数
printf("\n总共有%d个", count);
return 0;
}
方法2、利用平方根求解
一个数m能够写成a*b的方式的时候，a和b中至少有一个数字是小于等于m开平方的
例子：
16 = 2 * 8 = 4 * 4 ； 2<4 4<=√16
36 = 4 * 9 = 6 * 6； 4<6 6<=√36
32 = 4 * 8 ；4 < √32
所以说，能在开平方之前找到一个因子，那一定也能在开平方后面找到因子；反之，开平方前面找不到一个因子，那在开平方后面也一定找不到因子。
那我们每次计算，只需要试除到开平方m之前就行
代码及运行结果如下：
#include<stdio.h>
#include<math.h>
int main()
{
int a = 200;
int i = 0;
int j = 0;
int count = 0;
//遍历3~100之间的奇数
for (i = 101; i <= a; i+=2)
{
//设置标记
int flag = 1;
//试除开平方之前的数
//sqrt为开平方的库函数，需包含<math.h>的头文件
for (j = 2; j <= sqrt(i); j++)
{
if (i % j == 0)
{
//余数为0，标记改变
flag = 0;
break;
}
}
//if语句非0为真，查看标记是否改变
if (flag)
{
//统计个数
count++;
//打印素数
printf("%d ", i);
}
}
printf("\n有%d个素数", count);
}
这样就大大的减少了运算的次数，提高了效率，到这里也不妨看一下每种方法计算次数。
总结
代码通过一点一点的改良，我们可以明显看出，运算次数的减少。不要局限于固定思维，多看多学好的代码风格和代码，对自己提升更有帮助，希望这篇文章对大伙有帮助，看到这里了，不妨点个赞再走，哈哈，日后还会陆续更新文章，诚邀各位观看指点！文章来源：https://www.toymoban.com/news/detail-784527.html
提示：关于for循环
写法1是C语言的写法，写法2是C++的写法，当然这并不冲突。但建议我们在写C的时候，还是按照C的写法来。
文章来源地址https://www.toymoban.com/news/detail-784527.html
到了这里，关于C语言 | 素数求解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
