C语言素数判断算法优化与实现

1. 项目概述

素数判断是每个C语言初学者都会遇到的经典练习题。很多教材和入门教程中，通常会给出一个最基础的实现方案——遍历从2到i-1的所有整数来判断i是否为素数。这种"暴力遍历"的方法虽然直观易懂，但在实际应用中效率极低，特别是当需要处理大范围的数字时。

我在刚开始学习编程时也曾经困惑：为什么教科书上的解法运行起来这么慢？后来通过系统学习算法优化和数学原理，才发现原来素数判断有这么多可以优化的空间。今天我就以100-200这个区间为例，带大家从最基础的实现开始，逐步优化到一个高效的素数判断算法。

这个项目特别适合：

• 刚学完C语言基础语法，想提升编程思维的新手
• 对算法优化感兴趣，想了解如何用数学知识改进代码的开发者
• 需要准备编程面试，想巩固基础算法能力的求职者

2. 核心算法解析

2.1 素数的基础定义与判断

素数（又称质数）是指大于1的自然数，除了1和它本身外，不能被其他自然数整除。根据这个定义，最直观的判断方法就是：

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

这个方法虽然正确，但效率极低。比如判断101是否为素数，需要做99次除法运算（从2到100）。当n很大时，这种方法的耗时将变得不可接受。

2.2 第一次优化：缩小检查范围

观察素数的数学性质，我们可以发现一个重要规律：如果一个数n是合数（非素数），那么它一定可以表示为两个数的乘积，即n = a × b，其中a和b都不等于1或n本身。而且，这两个因数中必有一个小于等于√n，另一个大于等于√n。

这个规律的证明很简单：假设a和b都大于√n，那么a × b > √n × √n = n，这与n = a × b矛盾；同理，如果都小于√n，乘积会小于n。因此，要判断n是否为素数，我们只需要检查2到√n之间的整数是否能整除n即可。

在代码中，我们可以用i * i <= n来代替i <= sqrt(n)，这样可以避免使用浮点数运算：

c复制int isPrime(int n) {
    if (n <=