C++素数

判断素数——从分饼干到C++高效算法

素数（也叫质数） 是数学中一个神奇的概念。生活中，我们经常要分组分东西。比如6块饼干，可以分成2组每组3块，也可以分成3组每组2块，或者1组每组6块、6组每组1块——你看，它有很多种分法，除了“1组全部”和“每组1块”之外，还能有其他分法。
但有些数字就很“小气”，比如7块饼干，你只能分成1组每组7块，或者7组每组1块，再也找不到其他分组方式。这种只能被 1 和它本身 整除的大于1的自然数，就叫素数。最小的素数是2，它也是唯一的偶数素数。

在编程中，我们经常需要判断一个数是不是素数，比如用来加密、安排座位、分析数据等。下面我们就来学习如何用C++高效地判断素数。

关键概念讲解

1. 什么是“整除”和“因数”？

整除：如果整数 a 除以整数 b（b≠0）的余数为0，我们就说 b 能整除 a，b 是 a 的一个因数。
例子：12 ÷ 3 = 4 余0，所以3是12的因数；12 ÷ 5 = 2 余2，5不是12的因数。
素数：大于1的自然数，它只有两个因数：1和它本身。比如7的因数只有1和7，所以7是素数。而6的因数有1、2、3、6，共4个，所以6不是素数（叫合数）。

2. 为什么检查到平方根就够了？

你可能会想：判断一个数 n 是不是素数，最笨的办法就是从2试到 n-1，看看有没有能整除的。但这样太慢了，尤其当 n 是1亿时，要检查近1亿次！
优化原理：如果 n 有一个大于 √n 的因数 a，那么它一定有一个小于 √n 的因数 b，因为 a × b = n，所以 b = n / a，且 b < √n。
例：判断 100 是不是素数。√100 = 10。只需检查2~~10是否有因数。2能整除100，所以100不是素数。我们不需要检查20、25等，因为2已经在2~~10里了。
所以只需从2检查到 √n 即可，大大减少循环次数。

3. 奇偶性优化

除了2以外，所有偶数都不是素数（因为它们都能被2整除）。所以我们先单独处理2，然后只检查奇数因子（从3开始，每次加2）。这样循环次数又减少一半。

代码深度讲解

下面是一段完整、高效的C++判断素数函数，每行都加了中文注释：

#include <iostream>   // 用于输入输出
#include <cmath>      // 用于 sqrt 函数
using namespace std;  // 标准命名空间

// 判断素数的函数，返回 true 表示是素数
bool isPrime(int n) {
    if (n < 2) return false;          // 小于2的数（0、1、负数）不是素数
    if (n == 2) return true;          // 2是素数，特例
    if (n % 2 == 0) return false;     // 其他偶数都不是素数

    int limit = sqrt(n);              // 计算 n 的平方根（取整数部分）
    for (int i = 3; i <= limit; i += 2) { // 只检查奇数因子
        if (n % i == 0) {            // 如果 i 能整除 n
            return false;            // 则 n 不是素数
        }
    }
    return true;                     // 循环结束都没找到因数，n 是素数
}

int main() {
    int num;                         // 定义变量，存储用户输入的数字
    cout << "请输入一个正整数：";
    cin >> num;                      // 读取输入
    if (isPrime(num)) {
        cout << num << " 是素数。" << endl;
    } else {
        cout << num << " 不是素数。" << endl;
    }
    return 0;                        // 程序正常结束
}

要点解释：

第7行：n < 2 包括了0和1，它们既不是素数也不是合数，我们都返回 false。
第8行：2是唯一的偶数素数，单独处理。
第9行：排除所有大于2的偶数。
第11行：提前把 sqrt(n) 赋值给 limit，避免每次循环都重复计算平方根（虽然编译器可能优化，但养成好习惯）。
第12行：从3开始，步长为2，只检查奇数。注意 i <= limit 要取等号，比如 n=9，√9=3，需要检查i=3，才能发现9不是素数。
第13-15行：如果能整除，立即返回 false。

常见错误与注意事项

忘记处理小于2的情况
新手常常只写 if (n == 1) return false; 却忘记0和负数。其实简洁写法 if (n < 2) 一次性排除所有。
循环条件写成 i < sqrt(n) 而不是 i <= sqrt(n)
这样会漏掉平方根恰好是因数的情况（如n=25，√25=5，需要检查i=5才能发现），导致错误判断25为素数。
使用浮点数平方根可能导致精度问题
sqrt(n) 返回 double，在 for 循环中比较 i <= sqrt(n) 时，由于浮点数精度误差，可能多算一次或少算一次。更稳妥的做法是：for (int i = 3; i * i <= n; i += 2)。用 i * i <= n 代替 i <= sqrt(n)，避免浮点运算，同时更快（乘法比开方快）。
示例修改：
```
for (int i = 3; i * i <= n; i += 2) {
    if (n % i == 0) return false;
}
```
忘记排除所有偶数因子
如果只写循环 i++，会检查2、4、6等偶数因子，虽然也能得到正确结果，但白白浪费一半时间。我们的优化从3开始 i += 2 就跳过了偶数。
把“因数”和“质因数”混淆
注意判断素数只关心是否存在非1非自身的因数，不关心这些因数是不是素数。比如6的因数2是一个素数，但不影响6是合数。

完整可运行示例

下面是一个完整的程序，包含更详细的输出，可以多次输入（输入0退出）：

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

// 判断素数的函数
bool isPrime(int n) {
    if (n < 2) return false;          // 小于2的不是素数
    if (n == 2) return true;          // 2是素数
    if (n % 2 == 0) return false;     // 偶数（除2外）不是素数
    for (int i = 3; i * i <= n; i += 2) { // 只检查奇数因子，避免浮点数
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int num;                         // 存储用户输入
    cout << "素数检测器（输入0退出）" << endl;
    while (true) {
        cout << "请输入一个正整数：";
        cin >> num;
        if (num == 0) {
            cout << "再见！" << endl;
            break;
        }
        if (isPrime(num)) {
            cout << num << " 是素数。" << endl;
        } else {
            cout << num << " 不是素数。" << endl;
        }
    }
    return 0;
}

测试示例：

输入 2 → 素数
输入 1 → 不是素数
输入 17 → 素数
输入 100 → 不是素数
输入 0 → 退出