整除、因数与质数——数字的“亲戚”关系

你有没有想过，数字之间也有“亲戚”关系？有的数字能“整除”另一个，就像父母能完全分给孩子糖果一样。学习整除、因数和质数，就像是给数字们“认亲戚”。这些概念是数论里最基础的知识，也是以后学习密码学、分数运算、求最大公约数等内容的起点。

什么是整除？

如果 a 除以 b 能除尽（没有余数），我们就说 b 整除 a，记作 b | a。比如：12 块饼干平均分给 3 个小朋友，每人 4 块，没有剩余，那么 3 整除 12。

反过来，也可以说 a 是 b 的倍数，b 是 a 的因数（也叫约数）。

生活中的例子：

• 你有 20 元零花钱，想买 5 元一支的笔，可以买 4 支，花光所有钱，所以 5 整除 20。
• 班上有 30 人，要分成 4 人一组做游戏，30 ÷ 4 = 7 组余 2 人，不能完全分完，所以 4 不整除 30。

判断整除的小技巧：用 % 运算符，如果 a % b == 0，说明整除。

int a = 20;     // 总数
int b = 5;      // 每份大小
if (a % b == 0) {
    cout << b << " 整除 " << a << endl;
} else {
    cout << b << " 不整除 " << a << endl;
}

因数和倍数——数字的“父子”关系

因数

一个数的因数就是能整除这个数的所有正整数。比如：

• 12 的因数有：1, 2, 3, 4, 6, 12（因为 12÷1=12，12÷2=6，……）
• 8 的因数有：1, 2, 4, 8
• 7 的因数只有：1, 7

注意：1 是所有正整数的因数，但 0 的因数没有意义（因为不能除以 0）。

倍数

如果 a 是 b 的倍数，那么 a = b × k（k 是正整数）。比如：

• 3 的倍数：3, 6, 9, 12, 15 ...
• 5 的倍数：5, 10, 15, 20 ...

要点：一个数的倍数有无限个，而因数个数是有限的。

找因数的代码：

#include <iostream>
using namespace std;

int main() {
    int num = 12;                 // 要找因数的数字
    cout << num << " 的因数有：";
    for (int i = 1; i <= num; i++) {  // i 从 1 试到 num
        if (num % i == 0) {           // 如果 i 能整除 num
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

运行结果：12 的因数有：1 2 3 4 6 12

质数与合数——数字中的“原子”

质数（素数） 是大于 1 的自然数，并且只有 1 和它本身两个因数。比如：

• 2：因数只有 1 和 2 → 质数
• 3：因数只有 1 和 3 → 质数
• 5、7、11、13 都是质数

合数 是大于 1 的自然数中，除了 1 和它本身，还有别的因数。比如：

• 4：因数有 1, 2, 4 → 合数
• 6：因数有 1, 2, 3, 6 → 合数
• 9：因数有 1, 3, 9 → 合数

特别注意：1 既不是质数也不是合数，因为它只有一个因数。

生活类比：质数就像搭积木的最小零件（比如乐高最小块），其他数字（合数）可以用这些“零件”拼出来。例如 6 = 2 × 3，2 和 3 就是质数零件。

如何判断一个数是不是质数？——试除法

基本方法

假设要判断 n 是不是质数（n > 1）。从 2 开始，一直到 n-1，检查每个数 i 是否能整除 n。如果有一个能整除，说明 n 有除了 1 和它本身之外的因数，n 就是合数；如果全都不整除，n 就是质数。

但是，如果 n 很大（比如 1000000），循环要跑 100 万次，太慢了！所以需要优化。

优化：只试到 √n

为什么可以只试到 √n 呢？

如果 n 有一个大于 √n 的因数 d，那么 n / d 一定小于 √n，而且也是 n 的因数。比如 n = 100，√100 = 10。假设一个因数是 20（大于 10），那么另一个因数是 100÷20=5（小于 10）。所以我们只要检查到 10，就能找到 5，从而判断 100 不是质数。反过来，如果直到 √n 都没找到因数，那么 n 就是质数。

数学证明：如果 n = a × b，且 a ≤ b，那么 a ≤ √n，b ≥ √n。所以只需检查 a 从 2 到 √n 即可。

循环条件写成 i * i <= n 或者 i <= sqrt(n)，但用 i * i <= n 可以避免浮点数误差。

处理特殊情况

• n < 2：不是质数（0 和 1 都不是质数）
• n = 2：是质数（最小的质数）
• 偶数：除了 2 以外，所有偶数都不是质数（因为它们都有因数 2）。可以再优化：先排除偶数，然后只检查奇数。

不过对于初学者，先掌握最基础的试除法即可。

完整示例代码（带详细注释）

#include <iostream>
using namespace std;

// 函数：判断一个数是不是质数
bool isPrime(int n) {
    if (n < 2) return false;          // 0 和 1 不是质数
    for (int i = 2; i * i <= n; i++) { // i 从 2 试到 √n
        if (n % i == 0) {             // 如果 i 能整除 n，说明 n 有因数
            return false;             // 不是质数，直接返回
        }
    }
    return true;                      // 没有找到因数，是质数
}

int main() {
    int num;                          // 要判断的数字
    cout << "请输入一个正整数：";
    cin >> num;

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

运行测试：

• 输入 17 → 输出 17 是质数。
• 输入 18 → 输出 18 不是质数。
• 输入 1 或 0 → 输出 1 不是质数。 0 不是质数。
• 输入 2 → 输出 2 是质数。

新手容易犯的错误

1. 忘记处理 n < 2：0 和 1 都不是质数，但循环里 i 从 2 开始，如果 n = 1，循环条件 i * i <= 1 一开始就不成立，直接返回 true，结果错误。所以必须单独判断。
2. 循环条件写成 i <= n：虽然也能得到正确结果，但效率低，尤其 n 很大时会超时（比如 n = 10^9）。
3. 使用 sqrt(n) 需要 #include <cmath>：而且 sqrt 返回浮点数，用 i * i 更安全，不用引入额外头文件。
4. 把 1 当成质数：记住质数定义是“大于 1”，1 只有 1 个因数，不是质数。
5. 把 2 当成不是质数：2 是质数，而且是最小的质数，也是唯一的偶质数。

相关知识点指引

学会了判断质数，你可以继续探索：

• 分解质因数：把一个合数拆成质数相乘的形式，比如 12 = 2 × 2 × 3。
• 最大公约数和最小公倍数：用辗转相除法（欧几里得算法）求两个数的最大公约数。
• 埃氏筛法：快速找出 1 到 N 之间所有质数的方法，适合解决大范围质数问题。
• 欧拉筛：更高级的筛法，时间复杂度 O(N)。

质数就像数论世界里的“原子”，很多数学性质和算法都围绕它展开，比如 RSA 加密算法就是基于大质数的乘积难以分解来保护你的网络数据安全。掌握好这些基础，以后学习会更轻松！