2-07. 素因子分解（20） （ZJUPAT 数学）

题目链接：http://pat.zju.edu.cn/contests/ds/2-07

给定某个正整数N，求其素因子分解结果，即给出其因式分解表达式 N = p₁^k₁ * p₂^k₂ *…*p_m ^k_m。

输入格式说明：

输入long int范围内的正整数N。

输出格式说明：

按给定格式输出N的素因式分解表达式，即 N = p₁^k₁ * p₂^k₂ *…*p_m ^k_m，当中p_i为素因子并要求由小到大输出，指数k_i为p_i的个数；当k_i==1即因子p_i仅仅有一个时不输出k_i。

例子输入与输出：

序号输入输出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; }

转载于:https://www.cnblogs.com/bhlsheji/p/4366567.html