The words written in front
大家好，我是xiaoxie,希望你看完之后对你能有所帮助，不足之处，请批评指正！
希望可以和大家一起交流学习进步！
Introduction
大家都知道：“质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数，那如果我们想知道1–200之间的素数是什么，那该如何用C语言去解决这个问题呢。
一 算法介绍——试除法
试除法是一种简单而直观的质数判定方法。其基本思想是：对于正整数n，若n能被2到n-1之间的任一整数整除，则n非质数；否则，n为质数。
以下是基于试除法算法的C语言实现：
#include<stdio.h>
#include<math.h>
int main()
{
int n = 0;
int count1 = 0;//计算素数个数
for (n = 100; n <= 200; n++)
{
int j = 0;
for (j = 2; j <n; j++)
{
if (n % j == 0)//说明有除n和n本身的其他数整除，说明i不是素数
break;
}
if (j ==n)//说明2到n-1中没有n的因子
{
printf("%d\n", n);
count1++;
}
}printf("\ncount1=%d", count1);
return 0;
}
要想知道上面的时间复杂度，我们可以看它到底for循环了几次。我们可以对上述的代码增加一个对循环次数的监视，这样就可以直观的了解这段代码高不高效
代码实现如下：
#include<stdio.h>
#include<math.h>
int main()
{
int n = 0;
int count1 = 0;//计算素数个数
int count2 = 0;//计算循环次数
for (n = 100; n <= 200; n++)
{
int j = 0;
for (j = 2; j <n; j++)
{
count2++;
if (n % j == 0)//说明有除n和n本身的其他数整除，说明i不是素数
break;
}
if (j ==n)//说明2到n-1中没有n的因子
{
printf("%d\n", n);
count1++;
}
}printf("\ncount1=%d", count1);
printf("\ncount2=%d", count2);
return 0;
}
由此我们可以得出这段代码仅仅只是100个数就循环了3292次，而我们判断一个算法是否优劣是看它是否高效，执行效率是否高效。所以我们应该对它做出优化。
二试除法优化版–开平方
n=a*b,例如16=2*8=4*4，意味着a和b中至少有一个数字<=开平方n，如果在开平方之前仍未找到能整除i的数，就不可能再找到其他的数整除i,则该数为素数.以下是代码实现：
#include<stdio.h>
#include<math.h>
int main()
{
int n = 0;
int count1 = 0;//计算素数个数
int count2 = 0;//计算循环次数
for (n = 100; n <= 200; n++)
{
int j = 0;
for (j = 2; j <= sqrt(n); j++)//使用sqrt库函数要引用#include<math.h>
{
count2++;
if (n % j == 0)//说明有除n和n本身的其他数整除，说明i不是素数
break;
}
if (j>sqrt(n))//说明2到根号n中没有n的因子
{
printf("%d\n", n);
count1++;
}
}printf("\ncount1=%d", count1);
printf("\ncount2=%d", count2);
return 0;
}
由上述代码我们大大的优化算法的执行效率，减少了程序实现功能的时间。
三试除法优化版–去偶数
由素数定义我们可知素数只能被1和它本身整除那么只要n为偶数就一定不是素数，由此我们就可以从源头排除一些数。以下是代码实现：
#include<stdio.h>
#include<math.h>
int main()
{
int n = 0;
int count1 = 0;//计算素数个数
int count2 = 0;//计算循环次数
for (n = 100; n <= 200; n++)
{
if (n % 2 == 0)//判断n是否为偶数
{
continue;
}
int j = 0;
for (j = 2; j <= sqrt(n); j++)//使用sqrt库函数要引用#include<math.h>
{
count2++;
if (n % j == 0)//说明有除n和n本身的其他数整除，说明i不是素数
break;
}
if (j>sqrt(n))//说明2到根号n中没有n的因子
{
printf("%d\n", n);
count1++;
}
}printf("\ncount1=%d", count1);
printf("\ncount2=%d", count2);
return 0;
}
由此可见count2=342，只循环了342，又减少了程序实现功能的时间，提高了效率。所以博主强烈的建议大家掌握这个方法。这样你和其他的人做一道题时，直接就和其他人拉开了差距。那么判断素数就一种算法了嘛，接下来博主再为大家介绍一种算法
四埃拉托色尼筛选法
有些时候，除了检验给定整数x是否为质数的函数之外，如果能事先准备出质数数列或质数表，就可以帮助我们更有效地求解质数的相关问题。
埃拉托色尼筛选法（The Sieve of Eratosthenes）可以快速列举出给定范围内的所有质数，这个算法如下步骤生成质数表。
埃拉托色尼筛选法：
- 列举大于等于2的整数。
- 留下最小的整数2，删除所有2的倍数。
- 在剩下的整数中留下最小的3，删除所有3的倍数。
- 在剩下的整数中留下最小的5，删除所有5的倍数。
- 以下同理，留下仍未被删除的最小整数，删除该整数的倍数，一直循环到结束。
以最小的4个质数为例，其求解过程如图。
原始表：
第一轮：
第二轮：
第三轮：
第四轮：
根据上表提供的思路，我们可以用C语言实现这个算法的应用
代码如下:
#include <stdio.h>
#include <stdbool.h>
#define MAX 200
// 判断一个数是否为素数
bool is_prime(int num) {
if (num < 2) { // 如果一个数小于2，那么它不是素数
return false;
}
for (int i = 2; i * i <= num; i++) { // 遍历2到num的平方根
if (num % i == 0) {
// 如果num能被i整除，那么它不是素数
return false;
}
}
return true; // 如果num不能被2到它的平方根之间的任何数整除，那么它是素数
}
// 使用埃拉托色尼筛选法找出1到MAX之间的所有素数
void sieve_of_eratosthenes() {
bool is_prime[MAX + 1]; // 创建一个布尔类型的数组，用于存储1到MAX之间的所有数是否为素数
for (int i = 2; i <= MAX; i++) { // 将所有数初始化为素数
is_prime[i] = true;
}
int count = 0; // 记录循环次数
for (int i = 2; i * i <= MAX; i++) { // 遍历2到MAX的平方根
if (is_prime[i]) { // 如果i是素数
for (int j = i * i; j <= MAX; j += i) { // 将i的所有倍数标记为非素数
is_prime[j] = false;
}
count++; // 执行了一个完整的循环
}
}
printf("循环次数: %d\n", count); // 打印循环次数
for (int i = 2; i <= MAX; i++) { // 打印所有素数
if (is_prime[i]) {
printf("%d ", i);
}
}
}
// 主函数
int main() {
sieve_of_eratosthenes();
return 0;
}
埃拉托色尼筛选法需要占用一部分内存空间（与待检验整数的最大值N成正比），但其复杂度只有O(N log log N)。
总结
素数还有很多种算法可以求解，有句老话叫做”活到老学到老“，C语言更是一门需要不断学习，不断设计出更优解的语言，希望这篇文章可以帮助你对C语言的学习提供一点帮助，不足之处，请多多谅解，让我们一起共同学习共同成长。
文章出处登录后可见！
