【PAT】1059 Prime Factors (25分)（质因子分解）

1059 Prime Factors (25分)

#include<iostream>
#include<cmath>
using namespace std;#define maxn 10000005int prime[maxn], pnum=0;
bool p[maxn];struct factor{
    int x;		//质因子 int cnt;	//个数 
}fac[10];
//int最大数的质因子个数不会超过十个不同的，所以开10个数组足够了 
int fac_num= 0;void find_Prime(int n)//素数筛查 
{
    int sqt = (int)sqrt(1.0 * n);for(int i=2;i<=sqt;i++)if(!p[i]){
    prime[pnum++] = i;for(int j=i+i;j<=sqt;j+=i)p[j] = true;//true为合数 }
}void deal(int n)//处理 
{
    for(int i=0;i<pnum;i++){
    if(n % prime[i]==0){
    fac[fac_num].x = prime[i];fac[fac_num].cnt = 0;while(n % prime[i] == 0){
    fac[fac_num].cnt++;n /= prime[i];}fac_num++;}}if(n != 1){
    fac[fac_num].x = n;fac[fac_num++].cnt = 1;}
}int main()
{
    int num;cin>>num; if(num==1){
    cout<<"1=1"<<endl;return 0;	}find_Prime(num);deal(num);cout<<num<<"=";for(int i=0;i<fac_num;i++){
    cout<<fac[i].x; if(fac[i].cnt != 1)cout<<"^"<<fac[i].cnt;if(i!=fac_num-1)cout<<"*";}cout<<endl;return 0;
}