把 N(≤ 10¹²)分解为质因数的乘积,按要求格式化输出。
给定正整数 N(2 ≤ N ≤ 10¹²),输出它的因数分解式:
* 表示,左右各一个空格p^e(^ 左右不空格)例:6 = 2 * 3;20 = 2^2 * 5;23 = 23。
^ 周围不能有;指数为 1 时不输出 ^1。试除法分解格式输出边界处理long long
| 项目 | 说明 |
|---|---|
| 输入 | 一个正整数 N |
| 输出 | 一行因数分解式 |
| 数据范围 | 2 ≤ N ≤ 10¹² |
| 排序 | 质因数从小到大 |
| 格式 | 乘号写 * (左右各一空格);指数写 p^e |
while (t % p == 0) 统计次数 e * 先分解,再按格式拼接。
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"
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"
i 从 2 试到 √23 ≈ 4.8,都不整除
循环结束后 t = 23 > 1 → 因子 (23,1)
只有一个因子,前面不加乘号
指数为 1,所以只写 23
✅ 输出 "23"
| N | 质因数分解 | 因子列表 | 输出 |
|---|---|---|---|
| 6 | 2 × 3 | (2,1), (3,1) | 2 * 3 |
| 20 | 2² × 5 | (2,2), (5,1) | 2^2 * 5 |
| 23 | 23 | (23,1) | 23 |
| 8 | 2³ | (2,3) | 2^3 |
| 1000000000000 | 2¹² × 5¹² | (2,12), (5,12) | 2^12 * 5^12 |
^1——这是最常见的错误;② 乘号写成 * (左右各一空格),但 ^ 两侧不能有空格。对照着看:2^2 * 5。这是分解质因数的核心性质,务必理解。
如果 N 是合数,那么它一定有一个 ≤ √N 的质因子
因为若 N = a × b 且 a ≤ b,则 a ≤ √N
所以小的质因子一定能被试除发现
试除到 √N 后,如果还没有把 N 除到 1
说明剩下的 t 不可能再分解成两个 ≥ 2 的数
否则它们的乘积 ≥ (√N)² = N
所以剩下的 t 一定是质数
✅ 剩下的 t 直接作为质因子
N ≤ 10¹² → √N ≤ 10⁶
所以最多试除 10⁶ 次
每次循环还会快速缩小 t,实际更快
完全够快
i 从 2 试到 √t,找到因子就统计指数并除干净
(long long)i * i <= t,注意 t 在循环中会变小,所以条件是动态的。这样能自动减少循环次数。用埃氏筛打出质数表,再用质数去试除
| 方案 | 本题成本 | 代码量 |
|---|---|---|
| 试除法 | 约 10⁶ 次 | 约 15 行 |
| 筛法预处 | 约 10⁶ + 8 × 10⁴ | 约 25 行 |
输入一个正整数 N(2 ≤ N ≤ 10¹²),程序会分解并给出格式化的结果。
点按钮开始 →
#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。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 2 * 3 | 题面样例 1 |
20 | 2^2 * 5 | 题面样例 2 |
23 | 23 | 题面样例 3(质数) |
8 | 2^3 | 只有一个质因子,无乘号 |
2 | 2 | 最小值 |
1000000000000 | 2^12 * 5^12 | 最大值 10¹² |
%lld)。t > 1,必须把它输出。^1;乘号是 * (左右各一空格)。只用几个变量,不需要数组(输出直接拼接)。
✅ 最多约 100 万次试除,瞬间完成。
// 质因数分解(保存结果)的标准模板 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 变量 | 所有"用分隔符连接多项"的输出 |