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

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战(已更新的所有项目都能学习) / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新开坑项目:《Spring AI 项目实战》 正在持续爆肝中，基于 Spring AI + Spring Boot 3.x + JDK 21...， 点击查看 ;
• 《从零手撸：仿小红书（微服务架构）》 已完结，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

在编程学习的旅程中，练习实例是巩固理论知识的重要环节。C练习实例36 – 求100之内的素数 是一个经典且实用的编程任务，它不仅涉及数学逻辑的思考，还要求开发者掌握循环、条件判断等基础语法。对于编程初学者而言，这道题目能帮助理解算法设计的逻辑性；而对中级开发者来说，它也是一个优化代码效率的绝佳案例。本文将从素数的基本概念出发，逐步拆解问题，提供清晰的代码实现，并深入探讨如何通过优化算法提升性能。

一、素数的定义与数学基础

1.1 素数是什么？

素数（Prime Number）是指大于1的自然数中，除了1和它本身以外，无法被其他自然数整除的数。例如，2、3、5、7 是素数，而4（能被2整除）、9（能被3整除）则不是。我们可以将素数比喻为“数字世界中的原子”，因为它们无法被更小的自然数分解。

1.2 为什么需要求素数？

素数在密码学、数据安全等领域有广泛应用，例如RSA加密算法的核心就是基于大素数的分解难题。而本题的目标是“求100以内的素数”，虽然数值范围较小，但其核心逻辑可以拓展到更大的范围。

二、问题拆解与算法设计

2.1 问题分析

我们需要找出所有小于或等于100的素数。直观的思路是：

1. 遍历2到100之间的每一个数。
2. 对每个数判断是否为素数。
3. 将符合条件的数记录下来。

2.2 如何判断一个数是否为素数？

对于一个数n，若存在除1和它本身之外的因数，则它不是素数。因此，判断素数的核心逻辑是：

• 从2开始，遍历到n-1，检查是否存在能整除n的数。
• 若存在，则n不是素数；否则，是素数。

但这样的方法效率较低，可以通过数学优化减少计算量。

三、基础代码实现

3.1 基础版代码

以下是直接按照“遍历到n-1”的思路编写的代码：

#include <stdio.h>

int is_prime(int n) {
    if (n <= 1) return 0; // 小于等于1的数不是素数
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return 0; // 存在因数，不是素数
        }
    }
    return 1; // 是素数
}

int main() {
    printf("100以内的素数有：\n");
    for (int num = 2; num <= 100; num++) {
        if (is_prime(num)) {
            printf("%d ", num);
        }
    }
    return 0;
}

代码解释

• is_prime函数接收一个整数n，返回1（是素数）或0（非素数）。
• 当n小于等于1时，直接返回0（如1、0、负数）。
• 循环从2到n-1，若发现能整除n的数，立即返回0。
• 若循环结束未找到因数，则返回1。

输出结果

运行此代码将输出：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

四、算法优化与性能提升

4.1 优化点1：遍历到平方根

数学规律表明：如果n有一个大于其平方根的因数，那么必然存在一个小于平方根的对应因数。例如，对于n=25，因数5的平方根是5，因此只需检查到5即可。

修改后的is_prime函数如下：

int is_prime(int n) {
    if (n <= 1) return 0;
    int sqrt_n = (int)sqrt(n); // 计算平方根
    for (int i = 2; i <= sqrt_n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

优化效果

当n=100时，原方法需要遍历到99，而优化后仅需遍历到10，计算量减少了近90%！

4.2 优化点2：跳过偶数

除了2以外，所有偶数都不是素数。因此，在遍历因数时，可以只检查奇数：

int is_prime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1; // 2是唯一的偶数素数
    if (n % 2 == 0) return 0; // 排除其他偶数
    int sqrt_n = (int)sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2) { // 步长改为2，只检查奇数
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

综合优化效果

结合上述两点，算法的效率将显著提升。例如，当判断n=99时，原方法需要检查到98次，而优化后仅需检查到9次（平方根为9.949，取整后为9）。

五、进阶案例：生成素数表

5.1 使用数组记录结果

除了逐个输出，也可以将素数存储在数组中，便于后续处理。

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

#define MAX 100

int main() {
    int primes[MAX + 1] = {0}; // 初始化为0，素数标记为1

    for (int num = 2; num <= MAX; num++) {
        if (primes[num] == 0) { // 未被标记为非素数
            // 标记所有倍数为非素数
            for (int multiple = num * num; multiple <= MAX; multiple += num) {
                primes[multiple] = 1;
            }
        }
    }

    printf("100以内的素数：\n");
    for (int i = 2; i <= MAX; i++) {
        if (primes[i] == 0) {
            printf("%d ", i);
        }
    }
    return 0;
}

算法原理

• 这是“埃拉托斯特尼筛法”（Sieve of Eratosthenes）的简化版本。
• 初始化一个数组，初始值全为0。
• 从2开始，若当前数未被标记（即为素数），则标记其所有倍数为非素数。
• 最终，未被标记的数即为素数。

优势

此方法的时间复杂度为O(n log log n)，比逐个判断更高效，尤其适用于较大的范围（如求10000以内的素数）。

六、常见错误与调试技巧

6.1 错误1：遗漏边界条件

• 问题：未处理n=2的情况，导致2被错误标记为非素数。
• 解决：在判断偶数时，单独处理n=2。

6.2 错误2：平方根计算不准确

• 问题：使用sqrt()函数时未包含头文件<math.h>，或未强制类型转换。
• 解决：确保代码开头有#include <math.h>，并用(int)sqrt(n)获取整数部分。

6.3 调试技巧

• 逐步打印：在关键位置添加printf语句，观察中间变量的值。
• 单元测试：单独测试is_prime函数，例如：

  printf("is_prime(7) = %d\n", is_prime(7)); // 应输出1
  printf("is_prime(9) = %d\n", is_prime(9)); // 应输出0
  

七、扩展思考与应用场景

7.1 扩展问题

• 问题1：如何求1000以内的素数？
  • 答案：只需修改代码中的MAX值为1000，并确保内存足够。
• 问题2：如何统计某个范围内的素数数量？
  • 答案：在循环中增加计数器变量，例如：

    int count = 0;
    for (int num = 2; num <= 100; num++) {
        if (is_prime(num)) count++;
    }
    printf("共有%d个素数\n", count);
    

7.2 实际应用场景

• 密码学：RSA算法依赖大素数的乘积，其因数分解难度构成加密基础。
• 随机数生成：素数常用于构建伪随机数生成器的参数。
• 数据分块：在分布式计算中，素数可作为分块策略的优化参数。

结论

通过C练习实例36 – 求100之内的素数，我们不仅掌握了素数的基本判断方法，还学会了如何通过数学优化和算法设计提升代码效率。从基础的遍历法到高效的筛法，这一过程体现了编程中“先解决问题，再优化方案”的核心思想。对于开发者而言，理解素数的特性并灵活运用算法优化，是应对更复杂问题的关键。

建议读者动手实现不同版本的代码，并尝试扩展到更大的数值范围。通过实践，你将更深刻地理解算法的底层逻辑，并在编程之路上迈出坚实的一步。