"啊！为什么我写的素数判断代码总是不准？" 这估计是每个C语言新手都摔过跟头的地方。还记得我大学时交作业，因为把9判断成素数被教授当众点名，那尴尬劲儿现在想起来还脸红。今天咱们就掰开揉碎了说，新手到底该怎么正确写出又准又快的素数判断代码。

??先搞明白什么是素数??
说白了，素数就是只能被1和它本身整除的数。比如说2、3、5这些，但新手最容易栽在像9这样的数上——看着像奇数，其实能被3整除。判断素数的核心就两点：遍历可能的因数、确认有没有除了1和自身之外的约数。

??第一个方法：基础试除法??
刚入门时老师都教这个，就是从2到n-1挨个试除：

c复制
int isPrime(int n) {
    if(n <= 1) return 0;
    for(int i=2; iif(n%i == 0) return 0;
    }
    return 1;
}

但这个方法有个大坑！比如输入n=1时会误判，所以必须加上开头那个n<=1的判断。我见过至少十几个同学在这个地方翻车，运行结果死活不对还找不到原因。

??第二个方法：开平方优化??
老鸟们看到上面的代码估计要笑了——这也太慢了！其实只要试到sqrt(n)就行：

c复制
#include 
int isPrime(int n) {
    if(n <= 1) return 0;
    for(int i=2; i<=sqrt(n); i++){
        if(n%i == 0) return 0;
    }
    return 1;
}

这里有个疑问：为啥到平方根就够了？举个例子，36的因数对是(2,18)、(3,12)、(4,9)、(6,6)，后半截其实都是重复判断。这个优化能让循环次数从n次降到√n次，特别是处理大数时快得不是一星半点。

??第三个方法：埃拉托斯特尼筛法??
当需要找大量素数时，筛法才是王道。先创建个布尔数组，把非素数标记出来：

c复制
void sieve(int n){
    int isPrime[n+1];
    memset(isPrime,1,sizeof(isPrime));
    
    for(int i=2; i*i<=n; i++){
        if(isPrime[i]){
            for(int j=i*i; j<=n; j+=i)
                isPrime[j] = 0;
        }
    }
}

这个方法的时间复杂度只有O(n log log n)，比前两种强太多了。不过新手可能会懵：为啥内层循环从i*i开始？因为像i=2时，4、6、8这些合数已经被标记过了，不用重复处理。

??三种方法对比??

有人要问了：筛法这么好为啥不全用筛法？问得好！比如你只想判断单个大数是不是素数，用筛法反而浪费内存。这就好比杀鸡用牛刀，不是不行，但没必要。

??常见坑点实录??

• 忘了处理n=1的情况（必错）
• 把循环条件写成i
• 筛法初始化数组时没把0和1排除（内存溢出警告）
• 用奇数优化时漏掉2这个特殊素数（输出结果少一个）

说到这儿，突然想起之前有个学员问我："为啥我的筛法在n=100时输出103个素数？" 一查代码，好家伙，数组越界访问了相邻内存，这种bug真是防不胜防。

??小编观点??
新手建议先用开平方法练手，等理解透了再玩筛法。别看筛法效率高，里面的数学原理和边界条件处理够喝一壶的。另外多说一嘴，现在网上很多示例代码根本没考虑n=1这种特殊情况，跟着抄作业准保掉坑里。