PAT A1059 Prime Factors

我的解法

解题思路：首先先求出素数表，然后，定义一个结构体factor，存放该数n的质因数的素数部分和指数部分。用n除以素数表得出该数组。

#include <cstdio>
#include <cmath>

typedef long long ll;
const int maxn=100000;
const int pnum=500;
int prime[pnum],num=0;
bool p[maxn]={false};
ll n;

struct factor{
	int x,cnt;
}fac[10];

void Find_Prime(int n1){
	for(int i=2;i<maxn;i++){//注意此处不能用i*i
		if(!p[i]){
			prime[num++]=i;
			if(num>=n1) break; 
			for(int j=i+i;j<maxn;j+=i){
				p[j]=true;
			}
		}
	}
}

int main(){
	Find_Prime(pnum);
	scanf("%lld",&n);
//	for(int i=0;i<pnum;i++){
//		printf("i=%d:%d\n",i,prime[i]);
//	} 
	ll m=n;
	int fnum=0;
	for(int i=0;i<pnum&&prime[i]<=(int)sqrt(1.0*n);i++){
		if(n%prime[i]==0){
			fac[fnum].x=prime[i];
			fac[fnum].cnt=0;
			while(n%prime[i]==0){
				fac[fnum].cnt++;
				n/=prime[i];
			}
			fnum++;
		}
		if(n==1) break;//等于一的话直接中断循环
	}
	
	if(n!=1){//如果没有被根号n以内的质因子除尽
		fac[fnum].x=n;//那么一定只有一个大于根号n的质因子
		fac[fnum++].cnt=1;
	}
	
	if(m==1) printf("1=1");
	else{
		printf("%lld=",m);
		for(int i=0;i<fnum;i++){
		    if(i>0) printf("*");
            printf("%d",fac[i].x);
            if(fac[i].cnt>1) printf("^%d",fac[i].cnt);
        }
		
	}

	return 0;
}