GESP认证C++编程真题解析 | B3871 [GESP202309 五级] 因数分解

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3871 GESP202309 五级] 因数分解 - 洛谷

【题目描述】

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

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

【输入】

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

【输出】

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

【输入样例】

6

【输出样例】

2 * 3

【算法标签】

《洛谷 B3871 因数分解》 #数论# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1005;// 最大质因子数量intn;// 要分解的数inta[N],b[N];// a[i]存储第i个质因子，b[i]存储对应的指数intcur;// 当前质因子数量signedmain(){// 输入要分解的数cin>>n;// 质因数分解for(inti=2;i*i<=n;i++)// 只需检查到√n{if(n%i==0)// 如果i是n的因子{a[++cur]=i;// 记录质因子b[cur]=0;// 初始化指数// 计算指数：不断除以i直到不能整除while(n%i==0){b[cur]++;// 指数加1n/=i;// 除以质因子}}}// 处理剩余的部分// 如果n>1，说明n本身是一个质数if(n>1){a[++cur]=n;// 剩余的n是质因子b[cur]=1;// 指数为1}// 调试输出// for (int i = 1; i <= cur; i++)// cout << a[i] << ' ' << b[i] << endl;// 格式化输出质因数分解结果for(inti=1;i<cur;i++)// 前cur-1个因子{if(b[i]==1){cout<<a[i];// 指数为1，只输出因子}else{cout<<a[i]<<"^"<<b[i];// 指数大于1，输出指数形式}cout<<" * ";// 因子间用乘号连接}// 输出最后一个因子（不加乘号）if(b[cur]==1){cout<<a[cur];// 指数为1}else{cout<<a[cur]<<"^"<<b[cur];// 指数大于1}return0;}

【运行结果】

6 2 * 3