C 练习实例36 – 求100之内的素数（手把手讲解）

C 练习实例36 – 求100之内的素数

在学习 C 语言的过程中，我们常常会遇到一些经典的编程练习题，它们看似简单，却能帮助我们夯实基础、理解逻辑。今天要讲的这个题目，就是 C 练习实例36 – 求100之内的素数。它不仅是初学者掌握循环与判断的绝佳实践，也是一次对算法效率的初步探索。

素数，也叫质数，是指大于 1 且只能被 1 和自身整除的自然数。比如 2、3、5、7、11 都是素数，而 4、6、8、9 显然不是，因为它们能被其他数整除。我们今天的目标，就是用 C 语言找出从 2 到 100 之间所有的素数。

这个题目虽然看起来不大，但它背后涉及了三个核心知识点：循环控制、条件判断、以及算法优化。如果你是初学者，别担心，我会一步步带你理解，就像拆解一个积木玩具一样，把复杂逻辑拆成简单步骤。

什么是素数？从生活中的例子说起

想象一下你在分糖果。如果有 7 个糖果，你只能平均分给 1 个人或 7 个人，不能分成 2 份、3 份、4 份……这就说明 7 是一个“不可再分”的数，它就是素数。

反过来，如果 8 个糖果，你可以分给 2 个人，每人 4 个，也可以分给 4 个人，每人 2 个。这说明 8 可以被 2 和 4 整除，它就不是素数。

所以，判断一个数是不是素数，关键就是看它能不能被小于它的数整除。如果都不能，那就是素数。

基础思路：暴力枚举法

最直观的方法，就是对每个数从 2 到 n-1 逐一尝试能否整除。如果没有任何一个数能整除它，那它就是素数。

我们来写一个简单的程序，遍历 2 到 100 的每一个数，然后判断它是否为素数。

#include <stdio.h>

int main() {
    // 外层循环：遍历 2 到 100 的每一个数
    for (int i = 2; i <= 100; i++) {
        int is_prime = 1;  // 假设当前数是素数，用标志位标记

        // 内层循环：尝试用 2 到 i-1 的数去整除 i
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                is_prime = 0;  // 如果能整除，说明不是素数
                break;         // 一旦找到一个因数，立刻跳出循环
            }
        }

        // 如果标志位仍为 1，说明没有找到因数，是素数
        if (is_prime == 1) {
            printf("%d ", i);
        }
    }

    printf("\n");
    return 0;
}

代码注释详解：

• for (int i = 2; i <= 100; i++)：外层循环从 2 开始，一直到 100，我们检查每一个数。
• int is_prime = 1;：设置一个标志变量，初始为 1，代表“目前认为是素数”。
• for (int j = 2; j < i; j++)：内层循环尝试用 2 到 i-1 的数去整除 i。
• if (i % j == 0)：判断是否能整除，如果能，说明 i 有因数，不是素数。
• is_prime = 0; break;：一旦发现一个因数，就标记为非素数，并跳出内层循环，避免多余计算。
• if (is_prime == 1)：如果整个循环都没找到因数，说明是素数，打印输出。

这个方法虽然简单，但效率不高。比如判断 97 时，我们要从 2 试到 96，其实大可不必。

优化思路：减少判断范围

你有没有想过，如果一个数能被 6 整除，那它肯定也能被 2 或 3 整除。所以，我们不需要检查所有小于 i 的数，只需要检查到 √i 就够了。

为什么？因为如果 i 有一个大于 √i 的因数，那它必然有一个小于 √i 的因数。比如 100，它的因数有 10 和 10，而 √100 = 10。如果一个因数大于 10，另一个就一定小于 10。

所以，我们只需要检查从 2 到 √i 的数即可。

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

int main() {
    printf("100 之内的素数有：\n");

    for (int i = 2; i <= 100; i++) {
        int is_prime = 1;
        int limit = (int)sqrt(i);  // 计算 √i，只检查到这个值

        for (int j = 2; j <= limit; j++) {
            if (i % j == 0) {
                is_prime = 0;
                break;
            }
        }

        if (is_prime == 1) {
            printf("%d ", i);
        }
    }

    printf("\n");
    return 0;
}

优化亮点说明：

• #include <math.h>：引入数学库，使用 sqrt 函数。
• int limit = (int)sqrt(i);：计算 i 的平方根，并转为整数。
• j <= limit：循环只到 √i，大大减少了内层循环次数。

比如判断 97 时，我们只需检查 2 到 9 的数，而不是 2 到 96。效率提升了几十倍。

进阶技巧：使用数组标记法（埃拉托斯特尼筛法）

如果你觉得上面的方法还行，那我再告诉你一个更高效的方法——埃拉托斯特尼筛法（Sieve of Eratosthenes）。它就像用筛子过滤杂质，先把所有数都当成素数，然后逐步筛掉非素数。

算法步骤：

1. 创建一个布尔数组，大小为 101（索引 0 到 100），初始全部设为 true。
2. 从 2 开始，把 2 的所有倍数（4, 6, 8, ...）标记为 false。
3. 找到下一个未被标记的数（比如 3），把它的倍数也标记为 false。
4. 重复这个过程，直到处理完 √100 = 10。

最终，所有仍为 true 的索引，就是素数。

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

int main() {
    // 定义一个布尔数组，记录每个数是否为素数
    int is_prime[101];  // 索引 0 到 100
    memset(is_prime, 1, sizeof(is_prime));  // 初始全部设为 true

    // 0 和 1 不是素数
    is_prime[0] = 0;
    is_prime[1] = 0;

    // 埃拉托斯特尼筛法
    for (int i = 2; i * i <= 100; i++) {
        if (is_prime[i]) {  // 如果 i 是素数
            // 将 i 的所有倍数标记为非素数
            for (int j = i * i; j <= 100; j += i) {
                is_prime[j] = 0;
            }
        }
    }

    // 输出所有素数
    printf("100 之内的素数有：\n");
    for (int i = 2; i <= 100; i++) {
        if (is_prime[i]) {
            printf("%d ", i);
        }
    }

    printf("\n");
    return 0;
}

筛法核心逻辑解析：

• memset(is_prime, 1, sizeof(is_prime));：将数组初始化为 1，表示“默认是素数”。
• i * i <= 100：只需要从 2 到 10，因为大于 10 的数的平方已超过 100。
• j = i * i：从 i² 开始标记，因为更小的倍数已经被更小的素数筛过了。
• j += i：每次加 i，标记下一个倍数。

这个方法的时间复杂度是 O(n log log n)，远优于前两种方法的 O(n√n)。

结果对比：三种方法效率差异

我们来整理一下三种方法的优缺点：

在实际开发中，如果你要频繁查询 100 以内的素数，筛法是最优选择。如果你只是临时判断一个数是否为素数，优化枚举法就足够了。

实际应用：为什么素数很重要？

别小看素数，它在计算机领域应用广泛。比如：

• 加密算法（如 RSA）依赖大素数生成密钥。
• 哈希函数中，使用素数作为模数可以减少冲突。
• 游戏开发中，有时用素数作为随机种子的偏移量。

所以，掌握“C 练习实例36 – 求100之内的素数”不仅是学习 C 语言的里程碑，更是理解算法思维的起点。

总结与建议

今天我们从最简单的暴力法，一步步优化到高效的筛法，完整走了一遍求素数的全过程。你可能会问：我到底该用哪个？

答案是：理解优先，选择其次。

• 初学者：先用暴力法，理解逻辑。
• 中级开发者：尝试优化法，体会性能差异。
• 进阶者：掌握筛法，为复杂问题打基础。

编程不是背代码，而是培养思维。每一个练习题，都是一次思维的锻炼。

希望这篇文章能让你对“C 练习实例36 – 求100之内的素数”有更深入的理解。下次你再看到素数，不只是数字，而是一段段逻辑、一次次优化、一个个思维的跃迁。

动手写一写，跑一跑，改一改，你会发现，编程的乐趣，就藏在这些小小的练习里。