【GESP】C++五级真题（数论考点） luogu-B3871 [GESP202309 五级] 因数分解

GESP C++ 2023年9月五级真题，数论考点，难度⭐⭐★☆☆。洛谷难度等级普及−

luogu-B3871 [GESP202309 五级] 因数分解

题目要求

题目描述

每个正整数都可以分解成素数的乘积，例如： $6=2\times 3$，$20=2^2\times5$。

现在，给定一个正整数，请按要求输出它的因数分解式。

输入格式

输入第一行，包含一个正整数 $N$。约定 $2 \le N \le 10^{12}$。

输出格式

输出一行，为的因数分解式。要求按质因数由小到大排列，乘号用星号 * 表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头 ^ 表示，且左右不空格。

输入输出样例 #1

输入 #1

6

输出 #1

2 * 3

输入输出样例 #2

输入 #2

20

输出 #2

2^2 * 5

输入输出样例 #3

输入 #3

23

输出 #3

23

---

题目分析

解题思路

对 $N$ 做质因数分解，从小到大依次试除 $2 \rightarrow \sqrt{N}$：

1. 若 $i$ 能整除 $N$，则 $i$ 为质因子，统计其指数；
2. 每除尽一个因子就把 $N$ 更新为商，继续试除同一因子直至除不尽；
3. 若最终剩余 $N>1$，则该剩余值本身为质数，单独记录；
4. 按“质因子 * 质因子”格式输出，指数大于 $1$ 时用 ^ 合并，乘号左右各空一格。

在主思路一致的基础上，下面给出了两种不同的实现思路，对比它们的核心区别。

维度	方法一（边算边输出）	方法二（先存后输出）
输出时机	发现因子立即打印	全部因子收集完再统一打印
额外空间	几乎零额外空间	使用 vector 存储所有因子
代码复杂度	需维护 flag 控制首尾乘号	用下标天然控制分隔符
可扩展性	难以二次处理（如排序、格式化）	可任意后续处理（如逆序、去重、格式化）
可读性	输出与算法耦合，逻辑稍乱	算法与输出解耦，结构清晰

建议掌握：方法二

1. 思路清晰：先完整拿到数据，再决定如何展示，符合“计算-存储-展示”的分层思想。
2. 便于调试：可随时打印 factors 内容，快速定位因子分解是否正确。
3. 易扩展：若题目改为“从大到小输出”或“只输出指数大于 1 的因子”，只需改动最后遍历即可。
4. 竞赛习惯：在算法竞赛中，先收集再统一输出是通用模板，减少因格式错误丢分。

复杂度

试除范围 $2 \rightarrow \sqrt{N}$，单次试除 $O(\sqrt{N})$，总体 $O(\sqrt{N})$。

本题$N$的数据规模很大，若是$O(N)$的算法，会超时。

边界注意

• $N$ 本身就是质数时直接输出 $N$；
• 指数等于 $1$ 时不输出 ^1；
• 乘号前后必须各有一个空格，行首行尾无多余空格。

---

示例代码

方法一 直接输出

#include <cmath>
#include <iostream>

int main() {
    long long N;                // 读入待分解的正整数
    std::cin >> N;
    bool flag = false;          // 标记是否已输出过因子，用于控制乘号

    // 试除法枚举 2~√N 的所有可能因子
    for (long long i = 2; i <= std::sqrt(N); i++) {
        if (N % i == 0) {       // i 是 N 的一个质因子
            int count = 0;      // 统计该质因子出现的次数
            while (N % i == 0) {
                count++;
                N /= i;         // 将 i 完全除掉
            }
            if (flag) {
                std::cout << " * "; // 输出乘号，左右各空一格
            }
            flag = true;
            std::cout << i;     // 输出质因子
            if (count > 1) {
                std::cout << "^" << count; // 指数形式
            }
        }
    }
    // 若剩余 N>1，则它本身为质数，直接输出
    if (N > 1) {
        if (flag) {
            std::cout << " * ";
        }
        std::cout << N;
    }
    return 0;
}

方法二 保存因子，再输出

#include <vector>
#include <iostream>
#include <cmath>

int main() {
    long long N;
    std::cin >> N;                          // 读入待分解的正整数
    std::vector<std::pair<long long, int>> factors; // 存储质因子及其指数

    // 试除法枚举 2~√N 的所有可能因子
    for (long long i = 2; i <= std::sqrt(N); i++) {
        if (N % i == 0) {                   // i 是 N 的一个质因子
            int count = 0;                  // 统计该质因子出现的次数
            while (N % i == 0) {            // 将 i 完全除掉
                count++;
                N /= i;
            }
            factors.push_back({i, count});  // 记录质因子及其指数
        }
    }
    // 若剩余 N>1，则它本身为质数，单独记录
    if (N > 1) {
        factors.push_back({N, 1});
    }

    // 按格式输出质因数分解式
    for (size_t i = 0; i < factors.size(); i++) {
        if (i > 0) {
            std::cout << " * ";             // 输出乘号，左右各空一格
        }
        std::cout << factors[i].first;      // 输出质因子
        if (factors[i].second > 1) {
            std::cout << "^" << factors[i].second; // 指数形式
        }
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号