C++ 实例 – 判断素数（长文解析）

C++ 实例 – 判断素数：从零开始掌握基础算法逻辑

在学习 C++ 的过程中，你可能已经接触过变量、循环、条件判断这些基础语法。但真正考验你能否“活学活用”的，往往是那些看似简单、实则蕴含逻辑精髓的小项目。今天我们要动手实现一个经典问题：判断一个数是否为素数。这不仅是一个典型的 C++ 实例 – 判断素数的入门练习，更是理解算法效率与代码优化的绝佳起点。

素数，也叫质数，是指大于 1 且只能被 1 和自身整除的自然数。比如 2、3、5、7、11 都是素数，而 4、6、8、9 显然不是，因为它们有除了 1 和自身以外的因数。在编程世界里，判断素数就像在做“身份验证”——给定一个数，你要判断它是不是“纯净”的，即是否不被其他数“污染”。

这个任务听起来简单，但背后的逻辑设计却大有讲究。接下来，我们一步步拆解，从最朴素的思路，到优化后的高效实现，带你真正掌握 C++ 实例 – 判断素数的核心方法。

什么是素数？从数学定义到代码实现

在动手写代码之前，先让我们明确“素数”的数学定义：

一个大于 1 的自然数，如果除了 1 和它本身外，没有其他正因数，那么它就是素数。

比如：

5 ÷ 1 = 5，5 ÷ 5 = 1，中间没有整除的数 → 是素数 ✅
6 ÷ 2 = 3，说明 6 能被 2 整除 → 不是素数 ❌

这个定义，正是我们编写判断函数的“法律依据”。只要我们能验证：从 2 到 n-1 的所有数都不能整除 n，那 n 就是素数。

但注意，我们不需要检查到 n-1，因为一个数的因数不可能超过它的一半（除非是它本身）。比如 10 的因数最大是 5，12 的因数最大是 6。所以可以缩小范围，提高效率。

基础实现：暴力枚举法

我们先写一个最直观、最易理解的版本。这种方法虽然效率不高，但逻辑清晰，适合初学者理解算法本质。

#include <iostream>
using namespace std;

// 判断一个数是否为素数的函数
bool isPrime(int n) {
    // 如果 n 小于等于 1，不是素数
    if (n <= 1) {
        return false;
    }

    // 从 2 开始，检查到 n-1 是否能整除 n
    for (int i = 2; i < n; i++) {
        // 如果发现某个 i 能整除 n，说明 n 不是素数
        if (n % i == 0) {
            return false;
        }
    }

    // 如果没有找到因数，说明 n 是素数
    return true;
}

int main() {
    int num;

    // 提示用户输入一个数
    cout << "请输入一个正整数: ";
    cin >> num;

    // 调用函数判断
    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }

    return 0;
}

代码解析：

isPrime(int n)：函数接收一个整数，返回布尔值（true/false）。
if (n <= 1)：排除 1 和负数，因为素数定义从 2 开始。
for (int i = 2; i < n; i++)：遍历从 2 到 n-1 的所有整数。
n % i == 0：取模运算判断是否整除。如果余数为 0，说明能整除。
一旦找到一个因数，立即返回 false，避免无意义的后续检查。
如果循环结束都没找到因数，说明是素数，返回 true。

这个版本虽然逻辑清晰，但时间复杂度是 O(n)，当 n 很大时（比如 10 万），程序会卡住。我们需要优化。

优化思路：只检查到 √n

这里有一个重要的数学性质：如果一个数 n 有因数，那么至少有一个因数小于等于 √n。

举个例子：

36 的因数有：1, 2, 3, 4, 6, 9, 12, 18, 36
其中，小于等于 √36 = 6 的因数有：1, 2, 3, 4, 6
大于 6 的因数（如 9、12）都和小于 6 的因数“配对”出现

因此，我们只需检查从 2 到 √n 的数即可。如果都没有因数，那 n 一定是素数。

这个优化能将时间复杂度从 O(n) 降到 O(√n)，效率提升非常显著。

#include <iostream>
#include <cmath>  // 用于 sqrt 函数
using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    // 只需要检查到 sqrt(n)，提高效率
    int sqrtN = (int)sqrt(n);

    for (int i = 2; i <= sqrtN; i++) {
        // 如果 i 能整除 n，说明 n 不是素数
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int num;
    cout << "请输入一个正整数: ";
    cin >> num;

    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }

    return 0;
}

关键点说明：

#include <cmath>：引入 sqrt 函数，用于计算平方根。
(int)sqrt(n)：将浮点结果转换为整数，因为我们只关心整数范围内的因数。
i <= sqrtN：循环条件改为“小于等于平方根”，避免漏检。

这个版本已经非常适合实际应用了，尤其在处理 10^6 以内的数时依然很快。

进阶优化：处理偶数与 2 的特殊情况

我们发现，除了 2 以外，所有的偶数都不是素数。因为它们都能被 2 整除。

所以，可以先判断是否为 2（素数），是否为偶数（非素数），再对奇数进行检查。

这样可以跳过所有偶数，减少一半的判断次数。

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n == 2) {
        return true;  // 2 是唯一的偶数素数
    }

    if (n < 2 || n % 2 == 0) {
        return false;  // 小于 2 或是偶数（非 2）都不是素数
    }

    // 只检查奇数因数，从 3 开始，步长为 2
    int sqrtN = (int)sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int num;
    cout << "请输入一个正整数: ";
    cin >> num;

    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }

    return 0;
}

优化亮点：

n % 2 == 0：快速排除所有偶数。
i += 2：从 3 开始，只检查奇数，跳过偶数因数。
逻辑更精炼，效率更高，是实际项目中推荐的写法。

实际案例：打印 1 到 100 之间的所有素数

现在我们来实战一下：打印出 1 到 100 之间的所有素数。

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n == 2) return true;
    if (n < 2 || n % 2 == 0) return false;

    int sqrtN = (int)sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    cout << "1 到 100 之间的素数有：" << endl;

    int count = 0;  // 计数器，用于格式化输出
    for (int i = 1; i <= 100; i++) {
        if (isPrime(i)) {
            cout << i << " ";
            count++;
            // 每行输出 10 个数，换行
            if (count % 10 == 0) {
                cout << endl;
            }
        }
    }

    if (count % 10 != 0) {
        cout << endl;  // 最后一行换行
    }

    return 0;
}

输出结果（部分）：

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

这个例子展示了如何将判断素数的函数整合到循环中，形成一个完整的程序。这也是 C++ 实例 – 判断素数的经典应用场景。

总结与建议

通过今天的学习，我们从最基础的暴力判断，逐步优化到只检查到 √n，再到跳过偶数，最终实现高效、可复用的素数判断函数。

你可能会问：为什么一定要优化？
因为编程不仅仅是“能跑”，更是“跑得快”。一个 O(n) 的算法在处理大数据时可能要几秒甚至几分钟，而 O(√n) 可能在毫秒级完成。

记住，好的代码 = 正确性 + 效率 + 可读性。我们今天实现的 isPrime 函数，正是这三者的平衡典范。

最后，多练习、多调试，把 C++ 实例 – 判断素数这个经典题目吃透。它不仅是算法入门的敲门砖，也是你迈向更高阶编程能力的基石。

愿你在 C++ 的世界里，像素数一样纯粹而坚韧。