GESP 题解库 / 5 级题解 / [GESP202309 五级] 因数分解 · 第 18 / 23 题
GESP202309 五级 · B3871 · 简单

因数分解

把 N(≤ 10¹²)分解为质因数的乘积,按要求格式化输出。

📊
N ≤ 10¹²
数值范围
🔢
long long
数值类型
⚡
O(√N)
时间复杂度
🎯
试除法 + 格式控制
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定正整数 N(2 ≤ N ≤ 10¹²),输出它的因数分解式:

例:6 = 2 * 3;20 = 2^2 * 5;23 = 23。

💡
人话翻译:两步走——① 质因数分解(试除到 √N);② 按格式拼接字符串。难点其实在格式细节:乘号周围要有空格,但 ^ 周围不能有;指数为 1 时不输出 ^1。

🔍 关键词提取

试除法分解格式输出边界处理long long

已知条件

项目说明
输入一个正整数 N
输出一行因数分解式
数据范围2 ≤ N ≤ 10¹²
排序质因数从小到大
格式乘号写 * (左右各一空格);指数写 p^e

需要解决的问题

02
思维导图
整理解题思路的全貌
🔬 分解 + 格式化拼接
📥 读入
N ≤ 10¹²
必须用 long long
试除上限 √N
i 从 2 开始
🔬 分解
若 t % i == 0
循环统计指数 e
t 除以 i 的 e 次幂
记录 (i, e)
🧾 格式化
第一项前不加乘号
后续项前加 " * "
e == 1 只输出 p
e > 1 输出 "p^e"
⚠️ 易错点
用 int 读入(10¹² 溢出)
忘记最后剩余的大质因子
指数 1 输出了 ^1
乘号空格数不对
03
样例手算推导
三个样例的分解与输出

🧮 样例逐个走一遍

先分解,再按格式拼接。

1
N = 6

i = 2:6 % 2 == 0,统计到指数 1,t 变 3

i = 3:但此时 i × i = 9 > t = 3,循环结束

t = 3 > 1,把 3 作为最后一个质因子(指数 1)

因子列表:(2,1)、(3,1)

✅ 输出 "2 * 3"

2
N = 20

i = 2:20 % 2 == 0,连续除两次 → 指数 2,t 变 5

i = 3:i × i = 9 > t = 5,循环结束

t = 5 > 1 → 因子 (5,1)

因子列表:(2,2)、(5,1)

✅ 输出 "2^2 * 5"

3
N = 23(质数)

i 从 2 试到 √23 ≈ 4.8,都不整除

循环结束后 t = 23 > 1 → 因子 (23,1)

只有一个因子,前面不加乘号

指数为 1,所以只写 23

✅ 输出 "23"

📊 因子与输出格式对照

N质因数分解因子列表输出
62 × 3(2,1), (3,1)2 * 3
202² × 5(2,2), (5,1)2^2 * 5
2323(23,1)23
82³(2,3)2^3
10000000000002¹² × 5¹²(2,12), (5,12)2^12 * 5^12
🔑
格式的两个关键点:① 指数为 1 时不写 ^1——这是最常见的错误;② 乘号写成 * (左右各一空格),但 ^ 两侧不能有空格。对照着看:2^2 * 5。

🧮 为什么试除到 √N 就够

这是分解质因数的核心性质,务必理解。

1
性质

如果 N 是合数,那么它一定有一个 ≤ √N 的质因子

因为若 N = a × b 且 a ≤ b,则 a ≤ √N

所以小的质因子一定能被试除发现

2
推理

试除到 √N 后,如果还没有把 N 除到 1

说明剩下的 t 不可能再分解成两个 ≥ 2 的数

否则它们的乘积 ≥ (√N)² = N

所以剩下的 t 一定是质数

✅ 剩下的 t 直接作为质因子

3
复杂度

N ≤ 10¹² → √N ≤ 10⁶

所以最多试除 10⁶ 次

每次循环还会快速缩小 t,实际更快

完全够快

⚠️
这就是"最后剩余的大质因子"为什么必须单独处理:例如 N = 2 × 999983(999983 是大质数),试除 2 之后 t = 999983,而 √999983 ≈ 1000,循环会在 i = 1000 左右结束,此时 t 还没变成 1——所以必须把 t 作为最后一个质因子记录。
04
解法对比
试除法 vs 筛法预处理

⚔️ 解法对比

🟢 试除法(推荐) 推荐

i 从 2 试到 √t,找到因子就统计指数并除干净

  • 时间 O(√N) = 10⁶
  • 空间 O(1)
  • 代码 15 行
  • 不需要预处理
💡
实现要点:循环条件用 (long long)i * i <= t,注意 t 在循环中会变小,所以条件是动态的。这样能自动减少循环次数。

🟠 先筛出 10⁶ 以内的质数

用埃氏筛打出质数表,再用质数去试除

  • 预处理 O(10⁶ log log 10⁶)
  • 试除次数减少到 π(10⁶) ≈ 7.8 万
  • 代码多 10 行
  • 单次询问更快
⚠️
什么时候值得:本题只询问一次,打表 10⁶ 的预处理成本与直接试除相当,没必要。但如果需要分解很多个数(如 10⁵ 次),预处理质数表就非常划算。

📈 性能对比

方案本题成本代码量
试除法约 10⁶ 次约 15 行
筛法预处约 10⁶ + 8 × 10⁴约 25 行
05
算法流程图
试除统计因子并格式化输出
开始读入 N(long long);t = N;first = truei 从 2 开始,当 i × i ≤ t 时循环t % i == 0 吗?是 ✓统计指数 e,t 除以 i^e,输出该项否 ✗i 加 1循环结束后 t 是否大于 1?是 ✓把 t 作为一个质因子输出否 ✗结束结束i 加 1 继续试除
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔬 因数分解器

输入一个正整数 N(2 ≤ N ≤ 10¹²),程序会分解并给出格式化的结果。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    scanf("%lld", &n);

    long long t = n;
    bool first = true;          // 是否还没输出过任何因子

    for (long long i = 2; i * i <= t; i++) {
        if (t % i == 0) {
            int e = 0;
            while (t % i == 0) { t /= i; e++; }   // 统计指数并除干净

            if (!first) printf(" * ");             // 非首项前加 " * "
            first = false;

            if (e == 1) printf("%lld", i);         // 指数为 1,不写 ^1
            else        printf("%lld^%d", i, e);
        }
    }

    // 剩下的大质因子
    if (t > 1) {
        if (!first) printf(" * ");
        printf("%lld", t);
    }
    printf("\n");
    return 0;
}
🔑
i * i <= t 这个条件是动态的:因为循环中 t 会不断变小,上界也跟着缩小。比如 N = 20,除掉 2 之后 t = 5,此时条件变成 i * i <= 5,i = 3 时 9 > 5 就退出了——省掉了大量无用试除。另外注意用 long long 计算 i * i 防溢出。

📖 关键几行怎么看

代码作用为什么这样写
i * i <= t试除上界只需试到 √t,且 t 会变小
while (t % i == 0) { t /= i; e++; }统计指数除干净,保证 i 是质因子
if (!first) printf(" * ")控制乘号首项前不加乘号
if (e == 1)指数格式指数 1 不写 ^1
if (t > 1)剩余大质因子循环结束后 t 若 > 1 必为质数
⚠️
三个坑:① 用 int 读入(N 可达 10¹²,会溢出);② 忘记最后的 if (t > 1);③ 指数为 1 时也输出了 ^1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
62 * 3题面样例 1
202^2 * 5题面样例 2
2323题面样例 3(质数)
82^3只有一个质因子,无乘号
22最小值
10000000000002^12 * 5^12最大值 10¹²
✅
自查清单:① 用 long long 了吗?② 补了剩余因子吗?③ 格式完全对吗?

🚨 易错点清单

⚠️
用 int:N 可达 10¹²,必须用 long long(%lld)。
⚠️
漏掉最后的大质因子:循环结束后若 t > 1,必须把它输出。
⚠️
格式细节错:指数 1 不写 ^1;乘号是 * (左右各一空格)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(√N)
空间复杂度
O(1)
N 最大
10¹²
试除次数
≤ 10⁶

时间怎么算的?

空间都用在哪?

只用几个变量,不需要数组(输出直接拼接)。

✅ 最多约 100 万次试除,瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 质因数分解(保存结果)的标准模板
vector<pair<long long,int>> factorize(long long n) {
    vector<pair<long long,int>> res;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int e = 0;
            while (n % i == 0) { n /= i; e++; }
            res.push_back({i, e});
        }
    }
    if (n > 1) res.push_back({n, 1});      // 剩余大质因子
    return res;
}

// 由分解式还原出原数
long long restore(const vector<pair<long long,int>> &f) {
    long long r = 1;
    for (auto &p : f)
        for (int k = 0; k < p.second; k++) r *= p.first;
    return r;
}

// 输出格式控制要点
// - 首项前不加分隔符(用 first 标记)
// - 指数为 1 时省略 "^1"
// - 分隔符要用 " * "(左右各一空格)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
试除法分解试到 √n + 剩余因子所有质因数分解题
指数形式输出合并相同因子数学表达式输出、格式化题目
首项标记first 变量所有"用分隔符连接多项"的输出
🌟
思考题:如果题目要求输出因数的个数(即约数个数 d(N)),该怎么算?(提示:若 N = p₁^e₁ × p₂^e₂ × …,则约数个数 = (e₁+1)(e₂+1)…。因为每个质因数的指数可以独立取 0 ~ eᵢ——分解式一出来,约数个数、约数和都能顺带算出来。)