CC++ & Algorithm

C++质因数分解

较难11
语言版本：C++Python
概述：什么是质因数分解，以及如何用C++代码将一个合数分解成质因数的乘积。

拆数高手：学会用C++做质因数分解

什么是质因数分解？

你有没有玩过“拆积木”？把一个大的造型拆成几个小的标准积木块。质因数分解就像拆数字积木：把一个合数（比如12、30、100）拆成几个质数（比如2、3、5、7）相乘的形式。例如：

  • 12 = 2 × 2 × 3
  • 30 = 2 × 3 × 5
  • 100 = 2 × 2 × 5 × 5

这些乘法右边的数字全是质数，而且不能再拆了。为什么要做这件事？因为质因数就像是数字的“基本粒子”，很多数学问题（比如求最大公约数、判断两个数是否互质）都要用到它。生活中也可以类比：你有一堆糖果（合数），要平均分给几个小朋友，每个小朋友只能拿到同一种糖果（质数），看看能分成几种。

预备知识：质数和合数

要搞懂质因数分解，先分清两种数字：

  • 质数：只能被1和它自己整除的数，比如2、3、5、7、11……（1不是质数哦！）
  • 合数：除了1和它自己，还能被别的数整除，比如4、6、8、9、12……

质因数分解的目标就是：把一个合数写成质数相乘的形式。注意：1既不是质数也不是合数，所以分解时也不考虑1。

分解原理：从最小的质数开始试

想象你有一块橡皮泥（合数），你想把它捏成几个小圆球（质数）。你会先试试最小的圆球模具（数字2），能压出来就压一次，剩下的橡皮泥再继续压。如果2不行（不能被2整除），就换下一个模具3，再不行换5、7……直到剩下的橡皮泥自己就是一个圆球（质数）为止。

用数学语言说：从质数2开始，检查当前的数 n 能否被 i 整除。如果能，就输出 i，然后把 n 除以 i，继续用同样的 i 再试（因为同一个质数可能乘多次，比如8=2×2×2）。如果不能整除，i 增加1，继续试。当 i × i > n 时，停止循环——此时如果 n > 1，那么剩下的 n 本身就是一个质因子。

为什么当 i × i > n 就可以停？因为如果 n 有大于 √n 的因子，那么它一定还有一个小于 √n 的因子，我们已经试过了。所以最后剩下的 n 只能是1或者一个质数。

代码一步一步实现

下面我们写一个函数，把分解过程用C++表达出来。注意每个变量都加上中文注释，让代码自己会说话。

#include <iostream>
using namespace std;

void factorize(int num) { // num: 要分解的合数
    cout << num << " = ";
    int n = num; // n: 当前剩余未分解的数
    // 从最小的质数2开始试
    for (int i = 2; i * i <= n; i++) { // i: 当前尝试的除数（质数）
        while (n % i == 0) { // 如果n能被i整除
            cout << i << " * "; // 输出这个质因子
            n = n / i; // 除一次，得到新的n
        }
    }
    // 循环结束后，如果n大于1，说明n本身是一个质因子
    if (n > 1) {
        cout << n;
    }
    cout << endl;
}

int main() {
    int num; // 用户输入的数字
    cout << "请输入一个正整数：";
    cin >> num;
    factorize(num);
    return 0;
}

运行示例：

请输入一个正整数：12
12 = 2 * 2 * 3 *

咦，最后多了一个星号！这是因为我们在输出每个质因子时都加上了 " * "，最后一个因子后面也加了。这不太美观。我们可以改进一下：把因子先存到数组里，最后统一输出，或者用判断条件控制星号。下面给出一个更干净的版本。

优化版：去掉多余的乘号

#include <iostream>
#include <vector> // 用vector保存因子
using namespace std;

void factorize(int num) {
    cout << num << " = ";
    int n = num; // n: 当前剩余待分解的数
    vector<int> factors; // factors: 存放所有质因子
    for (int i = 2; i * i <= n; i++) { // i: 当前尝试的除数
        while (n % i == 0) {
            factors.push_back(i); // 把i加入因子列表
            n = n / i;
        }
    }
    if (n > 1) {
        factors.push_back(n); // 最后的质因子
    }

    // 输出因子，用" * "连接
    for (int j = 0; j < factors.size(); j++) {
        if (j > 0) cout << " * ";
        cout << factors[j];
    }
    cout << endl;
}

int main() {
    int num; // 用户输入的数字
    cout << "请输入一个正整数：";
    cin >> num;
    factorize(num);
    return 0;
}

运行结果：

请输入一个正整数：12
12 = 2 * 2 * 3

干净整齐！如果数字本身是质数（比如13），输出为 13 = 13，分解结果就是它自己。

生活例子来巩固

例子1：分零食
你有一袋100颗的糖果，想分成相同的小包，每包必须装一样多的糖果，而且每包的数量必须是质数。那么100可以拆成：100 = 2 × 2 × 5 × 5，也就是你可以分成4包，每包25颗（25不是质数，所以不能停）——但实际分解时，我们要的是最细的拆法，也就是2、2、5、5，你可以把它们看作“小包”的规格：先分成2包50颗，再每包分成2包25颗，再……直到每包5颗，最后5颗不能再分了。

例子2：找密码
老师给了一个数字360，让你分解成质因数。360 = 2 × 2 × 2 × 3 × 3 × 5。这可以用来快速求因数个数：每个质数的指数加1再相乘。比如360的因数个数 = (3+1)×(2+1)×(1+1) = 4×3×2=24个。

新手常犯的错误

  1. 忘记循环条件 i * i <= n 写成了 i <= n 这样会循环到很大，效率非常低，而且可能输出很多无意义的数字。记住，试到平方根就够了。

  2. while循环里没有改变n 如果忘记写 n /= i，会陷入死循环，不停输出同一个因子。

  3. 把1当作质数 有的同学看到最后if(n > 1)输出n，但如果输入的是1，程序会输出 1 = 然后什么也不显示。1不是合数也不是质数，不要对1做分解。

  4. 没有处理输入为负数或0 我们的代码只适用于正整数，如果输入负数或0，结果会混乱。可以加一个判断：if (num <= 1) { cout << "请输入大于1的整数\n"; return; }

完整可运行的最终代码（含输入检查）

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

void factorize(int num) { // num: 要分解的数
    if (num <= 1) {
        cout << num << " 无法分解质因数" << endl;
        return;
    }
    cout << num << " = ";
    int n = num; // n: 当前剩余待分解的数
    vector<int> factors; // factors: 存放所有质因子
    for (int i = 2; i * i <= n; i++) { // i: 当前尝试的除数
        while (n % i == 0) {
            factors.push_back(i);
            n = n / i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    // 输出结果
    for (int j = 0; j < factors.size(); j++) {
        if (j > 0) cout << " * ";
        cout << factors[j];
    }
    cout << endl;
}

int main() {
    int num; // 用户输入的数字
    cout << "请输入一个正整数（大于1）：";
    cin >> num;
    factorize(num);
    return 0;
}

你可以试试这些数字：

  • 100 → 2 * 2 * 5 * 5
  • 97 → 97 （质数，只输出自己）
  • 36 → 2 * 2 * 3 * 3
  • 2 → 2

继续探索

学会了质因数分解，你还可以挑战：

  • 用质因数分解求两个数的最大公约数（取公共质因数的较小指数）
  • 求最小公倍数（取所有质因数的较大指数）
  • 判断一个数是不是质数（如果分解后只有它本身，就是质数）
  • 更高效的方法：埃氏筛法先筛出所有质数，再用这些质数去分解，速度更快。

质因数分解是数论的基础，就像拆开乐高积木一样有趣。快去试试分解你学号、生日数字吧！

例题精讲

1单选题

以下哪个是数字 24 的质因数分解结果？

A2^3 × 3
B2^2 × 3^2
C2 × 3 × 4
D2^4 × 3
2单选题

用试除法对正整数 n（n>1）进行质因数分解时，循环的终止条件（即i的最大值）一般设为？

An / 2
Bn
Csqrt(n)
Dn - 1
3判断题

任何一个大于1的自然数都可以唯一地分解为质因数的乘积（不计相乘的顺序）。

4填空题
以下函数使用试除法输出正整数 n 的质因数分解结果（每输出一个因子后用空格隔开，最后输出换行）。请在 ___ 处补全代码。

void factor(int n) {
    for (int i = 2; ___; i++) {
        while (n % i == 0) {
            cout << i << " ";
            ___;
        }
    }
    if (n > 1) cout << n << endl;
}
5填空题
下面的代码利用while循环对 n（n≥2）进行质因数分解，按“质因子^指数”的格式输出（如输出 2^3 * 3^1）。请在 ___ 处补全代码。

void factor_exp(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (___ ) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << "^" << cnt << " * ";
        }
    }
    if (n > 1) cout << n << "^" << 1 << endl;
}