C 语言实例 – 判断素数（建议收藏）

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

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

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 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+ 小伙伴加入学习 ，欢迎点击围观

素数（Prime Number）是数学领域的基础概念，也是编程中常见的问题之一。在 C 语言中，判断一个数是否为素数不仅能够锻炼逻辑思维能力，还能帮助开发者理解循环、条件判断等核心语法。本文将以“C 语言实例 – 判断素数”为核心，从基础概念到优化算法，逐步展开讲解。通过实际代码案例和详细解析，帮助读者掌握不同场景下的素数判断方法，并提升代码效率。

什么是素数？

素数是指大于 1 的自然数中，除了 1 和它本身外，不能被其他自然数整除的数。例如，2、3、5、7 是素数，而 4（可被 2 整除）、6（可被 2 或 3 整除）则不是素数。素数的特性类似于“孤独的数字”——它们只能被 1 和自己“完全接纳”，无法与其他数形成“亲密关系”。

理解素数的定义是解决问题的第一步。接下来，我们将通过 C 语言代码实现这一判断逻辑。

基础版：循环到 n-1 的判断方法

实现思路

最直观的素数判断方法是：遍历从 2 到 n-1 的所有数，检查是否存在能整除 n 的数。若存在，则 n 不是素数；若不存在，则是素数。

代码示例

#include <stdio.h>  

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

int main() {  
    int number;  
    printf("请输入一个整数：");  
    scanf("%d", &number);  
    if (is_prime(number)) {  
        printf("%d 是素数。\n", number);  
    } else {  
        printf("%d 不是素数。\n", number);  
    }  
    return 0;  
}  

代码解析

1. 函数 is_prime：接受一个整数 num，返回 1（素数）或 0（非素数）。
2. 边界条件处理：若 num ≤ 1，直接返回 0。
3. 循环逻辑：从 2 开始遍历到 num-1，检查每个数是否能整除 num。
4. 时间复杂度：最坏情况下为 O(n)，例如当输入为质数时，需遍历所有数。

优化版：循环到 √n 的方法

实现思路

数学上，若一个数 n 有因数 a，则必然存在对应的因数 b = n/a。因此，只需遍历到 √n 即可覆盖所有可能的因数。例如，判断 25 是否为素数时，只需检查到 5（√25 = 5），因为 5 × 5 = 25。

代码示例

#include <stdio.h>  
#include <math.h> // 引入数学库，使用 sqrt() 函数  

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

int main() {  
    int number;  
    printf("请输入一个整数：");  
    scanf("%d", &number);  
    if (is_prime_optimized(number)) {  
        printf("%d 是素数。\n", number);  
    } else {  
        printf("%d 不是素数。\n", number);  
    }  
    return 0;  
}  

代码解析

1. 数学优化：通过 sqrt() 函数计算平方根，将循环范围缩小到 √n。
2. 时间复杂度：优化后为 O(√n)，例如判断 10000 时，仅需遍历到 100，效率提升显著。
3. 注意事项：
   • 需包含 <math.h> 头文件以使用 sqrt()。
   • 循环条件为 i <= sqrt_num，确保覆盖所有可能的因数。

进阶版：埃拉托斯特尼筛法（Sieve of Eratosthenes）

实现思路

埃拉托斯特尼筛法是一种高效生成素数列表的方法。其核心思想是：

1. 创建一个布尔数组 is_prime，初始值设为 true。
2. 从最小的素数 2 开始，将它的倍数标记为 false（非素数）。
3. 移动到下一个未被标记的数，重复上述步骤，直到处理完所有数。

此方法适用于批量判断一定范围内的素数，时间复杂度为 O(n log log n)。

代码示例

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

void sieve_of_eratosthenes(int n) {  
    bool is_prime[n + 1]; // 布尔数组初始化为 true  
    for (int i = 0; i <= n; i++) {  
        is_prime[i] = true;  
    }  
    is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数  

    for (int p = 2; p * p <= n; p++) {  
        if (is_prime[p]) { // 若当前数是素数  
            // 将它的倍数标记为非素数  
            for (int multiple = p * p; multiple <= n; multiple += p) {  
                is_prime[multiple] = false;  
            }  
        }  
    }  

    printf("2 到 %d 的素数如下：\n", n);  
    for (int i = 2; i <= n; i++) {  
        if (is_prime[i]) {  
            printf("%d ", i);  
        }  
    }  
    printf("\n");  
}  

int main() {  
    int limit;  
    printf("请输入范围上限：");  
    scanf("%d", &limit);  
    sieve_of_eratosthenes(limit);  
    return 0;  
}  

代码解析

1. 初始化数组：is_prime 数组初始全为 true，表示假设所有数均为素数。
2. 标记非素数：从 2 开始，将当前素数的所有倍数标记为 false。
3. 优化点：
   • 内层循环从 p*p 开始，因为更小的倍数已被之前的素数处理过。
   • 外层循环只需遍历到 √n，因为更大的因数已被覆盖。
4. 适用场景：当需要批量生成某一范围内的所有素数时，此方法比逐个判断更高效。

算法对比与选择指南

选择建议

• 单次判断小数：使用平方根优化法。
• 批量生成素数列表：使用埃拉托斯特尼筛法。
• 性能要求不高时：基础循环法可快速实现逻辑。

常见问题与调试技巧

1. 负数和 0 的处理

素数定义明确要求是大于 1 的自然数，因此在代码中需首先排除 num ≤ 1 的情况。例如：

if (num <= 1) {  
    return 0; // 非素数  
}  

2. 输入非整数的情况

C 语言中若输入非整数（如小数或字符），scanf 会因无法解析而陷入死锁。可通过添加错误处理或使用 fgets 结合 sscanf 提升健壮性。

3. 大数溢出问题

当输入极大数（如超过 INT_MAX）时，需改用 long long 类型或第三方大数库。例如：

#include <limits.h> // 定义 INT_MAX  

if (num > INT_MAX) {  
    printf("输入超出整型范围，请使用 long long 类型。\n");  
}  

结论

通过本文的讲解，读者可以掌握 C 语言中判断素数的三种核心方法，并根据实际需求选择最优方案。从基础的循环法到高效的筛法，每一步的优化都体现了编程中“以空间换时间”或“数学优化”的思维模式。建议读者通过实际编写代码加深理解，并尝试将这些方法应用于其他问题（如密码学中的质数生成）。

掌握素数判断不仅是学习算法的基础，更能帮助开发者在实际项目中提升代码效率。希望本文能成为您在“C 语言实例 – 判断素数”学习旅程中的实用指南！