分解N阶乘
将N!分解成质数幂的乘积
从标准输入读取一个整数N(2≤N≤5000),将N!的质数幂的乘积分解式打印到标准输出上,分解式中的质数按从小到大输出。对重复出现的质因数,用指数形式表示。
- 输入
-
输入有m+1行。第一行为测试数据的组数m,下面的m行分别为m组测试数据。
- 输出
-
输出有m行,分别对应输入的m组测试数据输出其阶乘的分解式
- 样例输入
-
1
-
5
- 样例输出
-
2^3*3*5
模拟题
#include <stdio.h> #include <stdlib.h> struct line{ int pn; int i; struct line * next; }; void decompoFactor (struct line *p,struct line *q,int n); int main() { int n; int k=2; struct line *root,*p,*q; int number,te; scanf("%d",&number); for(te=1;te<=number;te++) { k=2; scanf("%d",&n); if(n <2||n>5000){ printf(" error input"); return 0; } p=(struct line*)malloc(sizeof(struct line)); root=p; q=p; p->i=0; p->pn=2; p->next = NULL; //初始化p->next while (k<=n){ decompoFactor(p,q,k); k++; p=root; } p=root; if(p->i>1) printf("%d^%d",p->pn,p->i); else printf("%d",p->pn); p=p->next; while (p!=NULL){ if(p->i>1) printf("*%d^%d",p->pn,p->i); if(p->i==1) printf("*%d",p->pn); p=p->next; } printf("\n"); } return 0; } void decompoFactor (struct line *p,struct line *q,int n){// 分解因数; while (p!=NULL) { if((n%(p->pn))==0) { n=n/(p->pn); (p->i)++; } if(n%(p->pn)!=0) { q=p; p=p->next; } } if(p==NULL&&n!=1){ p=(struct line*)malloc(sizeof(struct line)); q->next=p; p->i=1; p->pn=n; p->next=NULL; p=q; } }