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

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

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

判断一个数是否为质数的原理相对简单，但实现高效的算法需要一些技巧。最基本的方法是试除法：对于一个待判断的数 n，我们可以尝试用 2 到 √n 之间的所有整数去除 n。如果在这个范围内找到了任何一个除数，那么 n 就不是质数；如果没有找到任何除数，那么 n 就是质数。
 

之所以只需要检查到 √n，是因为如果 n 不是质数，它的因数必定是成对出现的，其中一个小于或等于 √n，另一个大于或等于 √n。


下面是一个使用C语言实现的判断质数的函数：

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

bool is_prime(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 num;
    printf("请输入一个正整数：");
    scanf("%d", &num);

    if (is_prime(num)) {
        printf("%d 是质数\n", num);
    } else {
        printf("%d 不是质数\n", num);
    }

    return 0;
}

这段代码实现了一个名为 is_prime 的函数，它接受一个整数参数并返回一个布尔值，表示这个数是否为质数。函数的实现考虑了几个优化点：


最后，函数使用试除法检查从 3 到 √n 的所有奇数，如果找到任何一个除数，就返回 false，表示不是质数。如果没有找到除数，则返回 true，表示是质数。
 

main 函数演示了如何使用 is_prime 函数。它首先提示用户输入一个正整数，然后调用 is_prime 函数判断这个数是否为质数，最后输出判断结果。


这个程序的输出可能如下所示：

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

或者：

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

虽然这个算法对于判断单个数是否为质数已经足够高效，但如果需要找出一定范围内的所有质数，还有更高效的方法，比如埃拉托斯特尼筛法（Sieve of Eratosthenes）。这种方法可以在较短的时间内找出较大范围内的所有质数，特别适合于需要频繁判断质数的场景。

随着编程技能的提升，可以尝试实现更复杂和高效的算法，如米勒-拉宾素性检验（Miller-Rabin primality test）等，这些算法在处理大数时特别有用。同时，质数相关的问题也是许多编程竞赛和面试中常见的题目，因此掌握这些知识对于提升编程能力很有帮助。

相关文章