首页 > 代码库 > 2-07. 素因子分解（20） （ZJUPAT 数学）
2-07. 素因子分解（20） （ZJUPAT 数学）
题目链接：http://pat.zju.edu.cn/contests/ds/2-07
给定某个正整数N，求其素因子分解结果，即给出其因式分解表达式 N = p1^k1 * p2^k2 *…*pm ^km。
输入格式说明：
输入long int范围内的正整数N。
输出格式说明：
按给定格式输出N的素因式分解表达式，即 N = p1^k1 * p2^k2 *…*pm ^km，其中pi为素因子并要求由小到大输出，指数ki为pi的个数；当ki==1即因子pi只有一个时不输出ki。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 | 1024 | 1024=2^10 |
| 2 | 1323 | 1323=3^3*7^2 |
| 3 | 97532468 | 97532468=2^2*11*17*101*1291 |
| 4 | 1 | 1=1 |
| 5 | 3 | 3=3 |
代码如下：
#include <cstdio>
#include <cstring>
#include <cmath>
#define LL int
const int MAXN = 11117;
int main()
{
LL n;
int p[MAXN], k[MAXN];
while(~scanf("%d",&n))
{
LL tt = n;
memset(p,0,sizeof(p));
memset(k,0,sizeof(k));
int i = 2;
int cont = 0;
int flag = 0;
int l = 0;
if(n == 1)
{
printf("1=1\n");
continue;
}
while(n!=1)
{
while(n%i==0)
{
flag = 1;
cont++;
n /= i;
}
if(flag)
{
p[l] = i;
k[l] = cont;
l++;
flag = 0;
cont = 0;
}
i++;
}
printf("%d=",tt);
for(int i = 0; i < l-1; i++)
{
if(k[i] == 1)
printf("%d*",p[i]);
else
printf("%d^%d*",p[i],k[i]);
}
if(k[l-1] == 1)
printf("%d\n",p[l-1]);
else
printf("%d^%d\n",p[l-1],k[l-1]);
}
return 0;
}
2-07. 素因子分解（20） （ZJUPAT 数学）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。