跳到主要内容

AcWing 867. 分解质因数

本节目标

用试除法记录递增的质因数及其指数。

本题把质因数、约数与最大公约数的唯一分解落到可执行过程：每找到一个质因子，就一次除尽并记录它的指数。

查看 AcWing 原题

题意与约束​

对每个给定的正整数，按递增质因数顺序输出 质因数 指数，不同测试数据之间空一行。1 没有质因数，因此只输出对应的空行。

第一反应与瓶颈​

从 2 到原数 n 逐个试除，虽然能找出所有因子，但绝大多数候选并不需要检查。更重要的是，除去已发现的因子后，剩余值会缩小，循环边界也应随之收紧。

数学关系与算法推导​

从 2 起尝试 divisor。若它整除当前 n，反复相除并统计次数；这正是该质因子的指数。循环条件使用 divisor <= n / divisor，随剩余 n 缩小；不写 sqrt(n)，避免浮点舍入边界和整数平方溢出。

循环结束时，若剩余 n > 1，它不可能再有两个大于其平方根的因子，因此本身是一个尚未输出的大质因子，指数为 1。

正确性依据​

每次遇到可整除的 divisor 都将它除尽，所以记录的指数精确等于该因子在原数分解中的次数。所有不大于当前平方根的因子都被检查；剩余值若大于 1 则只能为质数。因子按递增枚举，输出顺序递增，且它们的乘积恢复原整数，故得到唯一的质因数分解。

样例执行过程​

分解 360：先除尽 2 得到指数 3、剩余 45；再除尽 3 得到指数 2、剩余 5；循环后剩余 5 是大质因子，结果为 (2,3)、(3,2)、(5,1)。

代码实现​

C++17
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> factors;

    for (int divisor = 2; divisor <= n / divisor; divisor++) {
        if (n % divisor != 0) {
            continue;
        }

        int exponent = 0;
        while (n % divisor == 0) {
            n /= divisor;
            exponent++;
        }
        factors.push_back({divisor, exponent});
    }
    if (n > 1) {
        factors.push_back({n, 1});
    }
    return factors;
}

#ifndef ALGORITHM_TUTORIAL_TEST
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    cin >> count;
    while (count--) {
        int n;
        cin >> n;
        for (const auto& [prime, exponent] : factorize(n)) {
            cout << prime << ' ' << exponent << '\n';
        }
        cout << '\n';
    }
}
#endif

核心函数返回按 (质因数, 指数) 排列的轻量二元组；入口负责题目要求的逐行和空行格式。

复杂度分析​

试除次数不超过当前数的平方根量级，时间复杂度为 O(√n)；除返回的因子表外，额外空间为 O(1)。

边界与易错点​

  • n = 1 应返回空表，不应输出 (1, 1)。
  • 因子必须在一次命中后除尽，否则指数会被拆成多条记录。
  • 循环结束后仍要检查剩余值，质数 97 正是这个分支。
  • 不用浮点 sqrt 决定边界，避免漏掉完全平方数和精度边界。

模式迁移​

知道质因数及指数后，可计算欧拉函数、约数个数或将分数约分。若有大量输入，先筛最小质因子能把单次试除进一步加速。