首页 > 编程笔记 > C语言笔记

C语言求100以内的质数（有源码有解析）

质数，也称为素数，是一个大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除。换句话说，质数只有两个因数：1 和它本身。例如，2、3、5、7、11 等都是质数。相对应的，能被 1 和它本身以外的数整除的数称为合数，如 4、6、8、9 等。
 

现在我们来探讨判断一个数是否为质数的原理。最简单直接的方法是从 2 开始，一直尝试到这个数的平方根，看是否有数可以整除它。
 

为什么只需要判断到平方根就够了呢？这是因为如果一个数 n 可以被因子 a 整除，那么 n 也一定可以被 n/a 整除，而 a 和 n/a 中必定有一个小于或等于 n 的平方根。因此，我们只需要检查到 √n 就可以了，这样可以大大减少判断的次数，提高程序的效率。


了解了这些基本概念，让我们来看看如何用C语言实现查找 100 以内所有质数的程序。我们将使用一个函数来判断一个数是否为质数，然后在主函数中遍历 2 到 100 之间的所有数字，调用这个判断函数，并打印出所有的质数。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    printf("100以内的质数有：\n");
    for (int i = 2; i <= 100; i++) {
        if (is_prime(i)) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

让我们逐步解析这段代码：
 

首先，我们引入了必要的头文件。<stdio.h> 用于输入输出，<stdbool.h> 引入了布尔类型，<math.h> 则是为了使用 sqrt() 函数计算平方根。
 

is_prime() 函数接受一个整数参数，返回一个布尔值，表示这个数是否为质数。在这个函数中，我们首先排除了小于或等于 1 的数，因为它们不是质数。然后，我们从 2 开始遍历到这个数的平方根，检查是否有数可以整除它。如果找到了这样的数，就说明它不是质数，返回 false。如果遍历结束后没有找到可以整除的数，就说明它是质数，返回 true。
 

在 main() 函数中，我们使用一个 for 循环遍历 2 到 100 之间的所有数字。对于每个数字，我们调用 is_prime() 函数进行判断。如果是质数，就将它打印出来。


运行这个程序，我们会得到如下输出：

100以内的质数有：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

这个程序虽然能够正确找出所有的质数，但在处理大范围的数时可能会比较慢。对于更大范围的质数查找，我们可以使用更高效的算法，比如埃拉托斯特尼筛法（Sieve of Eratosthenes）。这种方法的基本思想是：先把所有数标记为质数，然后从最小的质数开始，将它的所有倍数都标记为非质数。重复这个过程，直到处理完所有的数。


这个优化后的版本如下：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX 101

int main() {
    bool is_prime[MAX];
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i < MAX; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }

    printf("100以内的质数有：\n");
    for (int i = 2; i < MAX; i++) {
        if (is_prime[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

在这个优化版本中，我们使用了一个布尔数组来标记每个数是否为质数。初始时，我们假设所有的数都是质数（除了 0 和 1）。然后，我们从 2 开始，将每个质数的倍数都标记为非质数。最后，我们遍历数组，输出所有标记为质数的数。
 

这个方法的时间复杂度为 O(n log log n)，比之前的方法 O(n√n) 要快得多，尤其是在处理更大范围的数时。然而，它需要更多的内存来存储标记数组。这是一个典型的空间换时间的例子，展示了在编程中如何通过不同的算法来优化程序的性能。
 

通过学习这个例子，我们不仅掌握了如何在C语言中查找质数，还了解了如何优化算法以提高程序的效率。这种思维方式对于解决更复杂的编程问题非常重要，也是成为优秀程序员的关键之一。

相关文章