信息学奥赛一本通1210：因子分解

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

//2 16 3 81 18 60 79 97 100
//这道题学会的技巧：对数据的完备划分来写程序

int main()
{
    int n;
    cin>>n;
    int cnt=0;
    int m=n;
    while(n%2==0)
    {
        n=n/2;
        cnt++;
    }
    if(n==1) // if n initialized with 3 n will not be 1
    {
        if(cnt==1) //2
        {
            cout<<2<<endl;
            return 0;
        }
        if(cnt!=1) //16,32
        {
            cout<<2<<"^"<<cnt<<endl;
            return 0;
        }
    }
    
    if(n!=1&&cnt!=0)
    {
        if(cnt==1)
        {
            cout<<2<<"*";
        }
        if(cnt>1)
        {
            cout<<2<<"^"<<cnt<<"*";
        }
    }
    cnt=0;
    for(int i=3;i<=m;i+=2) //注意有可能是对质数分解，因此不是sqrt(m)
    {
        while(n%i==0)
        {
            n=n/i;
            cnt++;
        }
        if(cnt>1)
        {
            if(n==1)
            {
                cout<<i<<"^"<<cnt<<endl;
                break;
            }
            else{
                cout<<i<<"^"<<cnt<<"*";
            }
        }
        if(cnt==1)
        {
            if(n==1)
            {
                cout<<i<<endl;
                break;
            }
            else{
                cout<<i<<"*";
            }
        }
        cnt=0;
    }
    return 0;
}