C 语言实例 – 判断素数（千字长文）

C 语言实例 – 判断素数：从入门到实战

在学习 C 语言的过程中，判断一个数是否为素数，是一个非常经典又实用的编程练习。它不仅帮助我们理解基本的控制结构，还锻炼了逻辑思维能力。今天，我们就来深入剖析这个“C 语言实例 – 判断素数”的完整实现过程，结合多种方法，从最基础的思路逐步进阶，带你真正掌握其中的精髓。

什么是素数？理解问题本质

在开始写代码之前，先搞清楚“素数”到底是什么。素数，指的是大于 1 的自然数中，除了 1 和它本身以外，不能被其他任何正整数整除的数。

举个例子：

• 2 是素数（只能被 1 和 2 整除）
• 3 是素数（只能被 1 和 3 整除）
• 4 不是素数（能被 2 整除）
• 5 是素数（只能被 1 和 5 整除）

你可以把素数想象成“数学中的原子”——它们不能再被拆解成更小的整数乘积。而合数就像是由多个原子组成的分子。

这个概念虽然简单，但在编程中实现却很有讲究。我们不能靠“试”所有可能的除数，而要找到高效且准确的方法。

基础算法：暴力遍历法

最直观的方法，就是从 2 开始，一直试到 n - 1，看有没有能整除 n 的数。如果有，说明 n 不是素数；如果都没有，那就是素数。

下面是一个基础版本的代码实现：

#include <stdio.h>

// 判断一个数是否为素数的函数
int isPrime(int n) {
    // 小于等于 1 的数不是素数
    if (n <= 1) {
        return 0; // 返回 0 表示不是素数
    }
    
    // 从 2 开始，遍历到 n - 1
    for (int i = 2; i < n; i++) {
        // 如果能被 i 整除，说明不是素数
        if (n % i == 0) {
            return 0; // 提前返回，跳出函数
        }
    }
    
    // 如果循环结束都没找到因数，说明是素数
    return 1; // 返回 1 表示是素数
}

int main() {
    int num;
    
    printf("请输入一个整数：");
    scanf("%d", &num);
    
    // 调用函数判断
    if (isPrime(num)) {
        printf("%d 是素数\n", num);
    } else {
        printf("%d 不是素数\n", num);
    }
    
    return 0;
}

代码说明：

• isPrime 函数接收一个整数 n，返回 1 表示是素数，0 表示不是。
• if (n <= 1) 是边界处理，因为 1 和负数都不是素数。
• for (int i = 2; i < n; i++) 从 2 遍历到 n-1，检查是否有因数。
• n % i == 0 是取模运算，判断是否能整除。
• 一旦发现能整除，立即返回 0，节省时间。

这个方法逻辑清晰，适合初学者理解。但它的效率不高，比如判断一个 1000 的数，要循环 998 次。

优化思路：减少不必要的循环

我们能不能减少循环次数？答案是肯定的。

关键观察点：如果一个数 n 有因数 d，那么 d 和 n/d 一定成对出现。比如，如果 2 能整除 100，那么 50 也能整除 100。

这意味着，我们只需要检查到 √n 即可。因为如果 n 有大于 √n 的因数，那必然对应一个小于 √n 的因数。

例如：100 的平方根是 10，我们只需要检查 2 到 10 之间的数，如果没找到因数，那肯定没有。

优化后的代码如下：

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

int isPrime(int n) {
    if (n <= 1) {
        return 0;
    }
    
    // 只需检查到 sqrt(n)
    int sqrt_n = (int)sqrt(n);
    
    for (int i = 2; i <= sqrt_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;
}

优化点说明：

• 引入 math.h 头文件，使用 sqrt() 函数计算平方根。
• sqrt_n = (int)sqrt(n) 将浮点数转为整数，避免精度问题。
• 循环条件改为 i <= sqrt_n，大大减少循环次数。
• 对于 1000，原来要循环 998 次，现在只需 31 次左右，效率提升显著。

进阶技巧：处理特殊情况与边界

在实际开发中，我们不能只考虑“一般情况”。一些特殊情况必须提前处理，否则容易出错。

比如：

• 2 是唯一的偶数素数。
• 所有大于 2 的偶数都不是素数。

我们可以利用这一点进一步优化：先判断是否为 2，再判断是否为偶数。

int isPrime(int n) {
    if (n == 2) {
        return 1; // 2 是素数
    }
    
    if (n < 2 || n % 2 == 0) {
        return 0; // 小于 2 或偶数（除了 2）都不是素数
    }
    
    // 只检查奇数因数，从 3 开始，步长为 2
    int sqrt_n = (int)sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2) {
        if (n % i == 0) {
            return 0;
        }
    }
    
    return 1;
}

优化策略：

• 先处理 2 这个特例。
• 再排除所有偶数（除了 2），直接跳过。
• 循环从 3 开始，每次加 2，只检查奇数因数。

这样一来，循环次数再次减半，尤其对大数来说优势明显。

实际案例：找出 1 到 100 之间的所有素数

现在我们来做一个完整的应用：找出 1 到 100 之间的所有素数。

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

int isPrime(int n) {
    if (n == 2) return 1;
    if (n < 2 || n % 2 == 0) return 0;
    
    int sqrt_n = (int)sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    printf("1 到 100 之间的素数有：\n");
    
    int count = 0;
    for (int i = 1; i <= 100; i++) {
        if (isPrime(i)) {
            printf("%d ", i);
            count++;
            // 每行输出 10 个数，换行
            if (count % 10 == 0) {
                printf("\n");
            }
        }
    }
    
    printf("\n共找到 %d 个素数\n", count);
    
    return 0;
}

输出结果：

1 到 100 之间的素数有：
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 
共找到 25 个素数

这个案例不仅验证了我们的函数正确性，还展示了如何将“判断素数”应用到批量处理中。

性能对比：不同方法的效率差异

我们来做一个简单的性能对比表格，帮助你理解不同方法的差异：

从表格可以看出，优化后的算法在处理大数时优势非常明显。尤其在面试或竞赛中，这种优化思路常被考察。

总结：掌握核心思想，灵活应对

通过今天的“C 语言实例 – 判断素数”讲解，我们不仅学会了如何写一个判断函数，更重要的是理解了背后的数学逻辑和算法优化思想。

• 从暴力法到平方根优化，再到奇数跳过，每一步都是对效率的追求。
• 理解“因数成对出现”是关键洞察。
• 边界处理（如 2、1、负数）是编程中容易忽略但至关重要的部分。

记住：编程不是写代码，而是解决问题。一个好程序，不仅要能运行，还要高效、健壮、可维护。

最后，无论你是刚入门 C 语言的新手，还是有一定经验的开发者，希望这个实例能成为你算法思维训练的一块基石。下一次遇到类似问题，不妨多问一句：“能不能优化？”——这正是高手与普通程序员的区别。