C语言素数判断：从基础到优化的完整指南

1. C语言素数判断入门指南

第一次接触素数判断时，我盯着屏幕上的数字循环发了半小时呆。素数这个数学概念看似简单，但要用C语言准确实现却暗藏玄机。本文将带你从零开始，用最接地气的方式掌握素数判断的核心逻辑，并分享我在实际编程中踩过的那些坑。

素数（质数）是指大于1的自然数中，除了1和它本身外不再有其他因数的数。在密码学、哈希算法等领域有重要应用。用C语言实现素数判断，既是初学者练手的经典题目，也是理解循环控制和算法优化的绝佳案例。无论你是正在学习翁恺C语言课程的学生，还是准备计算机二级考试的考生，这篇指南都能让你少走弯路。

2. 素数判断的核心思路

2.1 基础判定原理

判断素数最直观的方法就是试除法：对于一个待判断的数n，用2到n-1之间的所有整数去试除。如果都不能整除，则n是素数。这个思路直接对应数学定义，但存在明显的效率问题。

c复制int isPrime_basic(int n) {
    if (n <= 1) return 0;  // 小于等于1的数不是素数
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return 0;  // 能被整除，不是素数
        }
    }
    return 1;  // 是素数
}

注意：初学者常忘记处理n<=1的特殊情况，这在PTA题库和计算机二级考试中都是高频扣分点

2.2 优化思路解析

试除法有三个关键优化点：

1. 只需检查到√n即可（数学证明：若n有大于√n的因数，必对应小于√n的因数）
2. 跳过偶数判断（2以外所有偶数都不是素数）
3. 提前检查小素数（2、3、5、7等）

优化后的代码效率可提升数十倍：

c复制int isPrime_optimized(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;  // 2是唯一的偶素数
    if (n % 2 == 0) return 0;  // 排除其他偶数
    for (int i = 3; i * i <= n; i += 2) {  // 只检查奇数
        if (n % i == 0