学步园

分解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;
	} 
}