C 练习实例33 – 质数（素数）判断（手把手讲解）

C 练习实例33 – 质数（素数）判断

在编程学习的道路上，质数判断是一个经典又实用的练习题。它看似简单，实则蕴含了算法思维的精髓。今天我们就来深入剖析 C 语言中“质数（素数）判断”这一经典题目，带你从零开始掌握它的核心逻辑与优化技巧。

质数，也叫素数，是指大于 1 且只能被 1 和自身整除的自然数。比如 2、3、5、7、11 都是质数，而 4、6、8、9 则不是，因为它们有除了 1 和自身以外的因数。这个概念听起来简单，但写成程序却考验着我们的逻辑严谨性。

在 C 语言中，我们可以通过循环与条件判断来实现这一功能。接下来，我们一步步拆解问题，从最基础的方法开始，再到优化版本，让你真正理解“质数判断”的底层原理。

基础思路：暴力枚举法

最直观的方法是“暴力枚举”——从 2 开始，一直试到 n - 1，看有没有能整除 n 的数。如果有，说明 n 不是质数；如果都没有，那就是质数。

我们先来看一个基础版本的代码：

#include <stdio.h>

int isPrime(int n) {
    // 如果 n 小于等于 1，直接返回 0（不是质数）
    if (n <= 1) {
        return 0;
    }

    // 从 2 开始，试到 n - 1
    for (int i = 2; i < n; i++) {
        // 如果 n 能被 i 整除，说明不是质数
        if (n % i == 0) {
            return 0;
        }
    }

    // 所有尝试都失败，说明是质数
    return 1;
}

int main() {
    int num;

    printf("请输入一个正整数：");
    scanf("%d", &num);

    // 调用判断函数
    if (isPrime(num)) {
        printf("%d 是质数。\n", num);
    } else {
        printf("%d 不是质数。\n", num);
    }

    return 0;
}

这段代码逻辑清晰，适合初学者理解。但有一个问题：效率太低。比如判断 1000000 是否为质数，要循环 999998 次，显然不现实。

优化思路一：减少判断范围

我们换个角度想：一个合数（非质数）的因数一定成对出现。比如 12 = 3 × 4，其中 3 < √12 ≈ 3.46，4 > √12。所以，我们只需要检查到 √n 就够了。

这就像你找一本书的作者，如果书的厚度是 100 页，你不需要翻完每一页，只要翻到第 10 页左右，如果没找到线索，那后面基本也不会有。因为如果真有，它早就出现在前面了。

于是我们优化如下：

#include <stdio.h>
#include <math.h>  // 用于 sqrt 函数

int isPrime(int n) {
    // 小于等于 1 的数不是质数
    if (n <= 1) {
        return 0;
    }

    // 2 是唯一的偶数质数
    if (n == 2) {
        return 1;
    }

    // 偶数（除了 2）都不是质数
    if (n % 2 == 0) {
        return 0;
    }

    // 只需检查从 3 到 sqrt(n) 的奇数
    for (int i = 3; i * i <= n; i += 2) {
        // 如果 n 能被 i 整除，说明不是质数
        if (n % i == 0) {
            return 0;
        }
    }

    // 没有找到因数，是质数
    return 1;
}

int main() {
    int num;

    printf("请输入一个正整数：");
    scanf("%d", &num);

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

    return 0;
}

关键优化点说明：

• i * i <= n 代替 i <= sqrt(n)，避免浮点运算，提升效率。
• 从 3 开始，每次加 2，只检查奇数，跳过所有偶数。
• 特殊处理 2 和偶数，避免重复判断。

这个版本的性能提升非常明显，判断 1000000 时，只需循环约 500 次。

优化思路二：埃拉托斯特尼筛法（Sieve of Eratosthenes）

如果我们要判断多个数字是否为质数，比如 1 到 1000 内的所有质数，那么“逐个判断”就显得低效了。这时，我们可以使用埃拉托斯特尼筛法，它是一种高效的批量生成质数的方法。

它的思想很像“过滤”：先把所有数都标记为“可能是质数”，然后从 2 开始，把 2 的倍数全部标记为“不是质数”，再找下一个未被标记的数（即 3），把 3 的倍数也筛掉，依此类推。

下面是实现代码：

#include <stdio.h>
#include <string.h>  // 用于 memset

#define MAX 1000  // 定义最大范围

void sieveOfEratosthenes(int n) {
    // 创建一个布尔数组，初始全部为 true（表示可能是质数）
    int isPrime[MAX + 1];
    memset(isPrime, 1, sizeof(isPrime));

    // 0 和 1 不是质数
    isPrime[0] = isPrime[1] = 0;

    // 从 2 开始筛
    for (int i = 2; i * i <= n; i++) {
        // 如果 i 是质数，就筛掉它的倍数
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                // 标记 j 为非质数
                isPrime[j] = 0;
            }
        }
    }

    // 输出所有质数
    printf("1 到 %d 之间的质数有：\n", n);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

int main() {
    int n;

    printf("请输入一个正整数（作为上限）：");
    scanf("%d", &n);

    sieveOfEratosthenes(n);

    return 0;
}

运行示例：

请输入一个正整数（作为上限）：30
1 到 30 之间的质数有：
2 3 5 7 11 13 17 19 23 29 

这个方法的时间复杂度是 O(n log log n)，非常适合批量处理。

实际应用场景对比

你可以根据实际需求选择合适的方法。比如在做算法题时，如果题目要求“判断 100 个数是否为质数”，那用筛法会更快；如果只是判断一个数，用优化版判断即可。

常见错误与调试建议

1. 忘记处理边界条件：比如 n = 1、n = 2，容易出错。务必在函数开头加上 if (n <= 1) 的判断。

2. 循环条件写错：比如写成 i <= n 而不是 i * i <= n，会导致超时或死循环。

3. 漏掉偶数判断：很多初学者会忘记 2 是唯一的偶数质数，导致 2 被错误判断为非质数。

4. 数组越界：在筛法中，如果 MAX 定义太小，会出错。建议根据实际需求合理设置。

总结与延伸思考

通过本篇“C 练习实例33 – 质数（素数）判断”的讲解，我们不仅学会了如何用 C 语言判断一个数是否为质数，更深入理解了算法优化的核心思想：减少冗余计算，利用数学规律。

从暴力枚举到优化判断，再到批量筛法，每一步都在提升效率。这正是编程的魅力所在——同一个问题，可以有多种解法，而我们的目标是找到“最合适”的那一个。

建议你动手运行代码，尝试不同的输入，观察输出结果。也可以尝试将筛法扩展到更大的范围，比如 10000，看看程序运行是否流畅。

编程不是死记硬背，而是不断思考与优化的过程。每一次对“质数判断”的深入，都是你算法思维的一次成长。

当你能熟练写出高效的质数判断代码时，你会发现，那些曾经看似复杂的算法题，其实都源于这些基础概念的巧妙组合。

保持练习，持续积累，你的编程之路会走得更稳、更远。