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

判断质数的C语言代码（附带解析）

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

判断一个数是否为质数的原理相对简单，我们只需要检查这个数是否能被比它小的数（除了 1）整除：如果能被整除，那么它就不是质数；如果不能被任何小于它的数整除，那么它就是质数。
 

然而，为了提高效率，我们可以做一些优化：我们只需要检查到这个数的平方根就足够了。这是因为如果一个数 n 是合数（非质数），那么它一定有一个小于或等于其平方根的因子。
 

现在，让我们来看一个使用C语言判断质数的代码示例：

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

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    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 的函数，它接受一个整数参数 n，并返回一个布尔值，表示这个数是否为质数。在这个函数中，我们首先处理了一些特殊情况：

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

在 main 函数中，我们首先提示用户输入一个正整数，然后调用 isPrime 函数来判断这个数是否为质数，最后输出结果。
 

这个程序的输出结果可能如下：

请输入一个正整数：17
17 是质数。

或者：

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

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

通过学习和理解这个判断质数的C语言程序，你能更好地理解函数、循环、条件语句等C语言的基本概念。

相关文章