PAT (Advanced Level) 1059. Prime Factors (25)

素因子分解。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<map>
#include<queue>
#include<string>
#include<stack>
#include<vector>
using namespace std;

long long n;

bool f(long long a)
{
    for(long long i=2;i*i<=a;i++)
        if(a%i==0) return 0;
    return 1;
}

struct X
{
    long long num;
    int tot;
}s[100];

int main()
{
    scanf("%lld",&n); int g=0;
    printf("%lld=",n);
    for(long long i=2;;i++)
    {
        if(f(n))
        {
            s[g].num=n;
            s[g].tot=1;
            g++;
            break;
        }
        if(n%i!=0) continue;
        if(f(i)==0) continue;
        s[g].num=i; s[g].tot=0;
        while(1)
        {
            if(n%i==0)
            {
                n=n/i;
                s[g].tot++;
            }
            else  break;
        }
        g++;
        if(n==1) break;
    }

    printf("%lld",s[0].num);
    if(s[0].tot>1) printf("^%d",s[0].tot);
    for(int i=1;i<g;i++)
    {
        printf("*");
        printf("%lld",s[i].num);
        if(s[i].tot>1) printf("^%d",s[i].tot);
    }
    printf("
");

    return 0;
}