判断一个数是不是素数的C语言（有源码有解析）

素数，也称为质数，是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。换句话说，素数只能被 1 和它自身整除。例如，2、3、5、7、11、13 等都是素数。相反，能被除 1 和自身之外的其他数整除的数被称为合数，如 4、6、8、9、10 等。
 

了解了素数的概念后，我们来探讨判断一个数是否为素数的原理。最直观的方法是从 2 开始，一直检查到这个数的平方根。为什么只需要检查到平方根呢？这是因为如果一个数 n 是合数，它一定可以表示为两个因子的乘积，即：

n = a * b

如果 a 和 b 都大于 √n，那么 a * b 就会大于 n，这显然是不可能的。因此，我们只需要检查到 √n 就足够了。如果在这个范围内没有找到可以整除该数的因子，那么这个数就是素数。

现在，让我们来看一个用C语言实现的判断素数的函数：

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

bool isPrime(int n) {
    if (n <= 1) return false;  // 1 和负数不是素数
    if (n == 2) return true;   // 2 是最小的素数
    if (n % 2 == 0) return false;  // 偶数（除了2）都不是素数

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

int main() {
    int number;
    printf("请输入一个正整数：");
    scanf("%d", &number);

    if (isPrime(number)) {
        printf("%d 是素数\n", number);
    } else {
        printf("%d 不是素数\n", number);
    }

    return 0;
}

这段代码首先定义了一个 isPrime 函数，它接受一个整数参数并返回一个布尔值，表示这个数是否为素数。在 main 函数中，我们从用户那里获取一个数，然后调用 isPrime 函数来判断它是否为素数。

让我们详细分析一下 isPrime 函数的实现：

我们首先排除了一些特殊情况。小于等于 1 的数不是素数，所以直接返回 false。2 是最小的素数，所以如果输入是 2，我们直接返回 true。对于大于 2 的偶数，我们知道它们都不是素数（因为它们都能被 2 整除），所以我们也可以直接返回 false。
 

接下来，我们使用一个 for 循环来检查从 3 到 √n 的所有奇数。我们只检查奇数是因为我们已经排除了所有的偶数。如果 n 能被任何这些数整除，那么它就不是素数，我们返回 false。如果循环结束后没有找到任何因子，那么这个数就是素数，我们返回 true。
 

这个算法的时间复杂度是 O(√n)，这比简单地检查到 n-1 的 O(n) 算法要高效得多。对于大多数实际应用来说，这个算法已经足够快了。但是，对于非常大的数或需要频繁判断素数的场景，还有更高效的算法，如 Miller-Rabin 素性测试。
 

让我们来看几个使用这个程序的例子：

请输入一个正整数：17
17 是素数

请输入一个正整数：24
24 不是素数

请输入一个正整数：2
2 是素数

请输入一个正整数：1
1 不是素数

通过这些例子，我们可以看到程序正确地判断了各种不同的情况，包括典型的素数、合数、最小的素数，以及特殊情况如 1。这个程序为初学者提供了一个很好的起点，不仅可以用来判断素数，还可以作为学习C语言基本语法和逻辑结构的例子。