202309-因数分解(luogu-B3871)

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

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

题目要求

题目描述

每个正整数都可以分解成素数的乘积，例如： $6=2\times 3$ ， $20=2^2\times5$ 。
现在，给定一个正整数，请按要求输出它的因数分解式。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

2 * 3

输入输出样例 #2

输入 #2

输出 #2

2^2 * 5

输入输出样例 #3

输入 #3

输出 #3

题目分析

解题思路

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

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

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

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

建议掌握：方法二

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

复杂度

试除范围 $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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

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

最后更新于 2025年10月21日

202309-巧夺大奖(luogu-B3872)