PAT1059 Prime Factors

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805415005503488

思路：筛素数+因式分解模板，很重要

注意n=1的情况

#include <iostream>
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define scl(x) scanf("%lld",&x)
#define scs(x) scanf("%s",x)
#define pri(x) printf("%d\n",x)
#define pri2(x,y) printf("%d %d\n",x,y)
#define prs(x) printf("%s\n",(x))
#define prl(x) printf("%lld\n",x)
#define ll long long
#define PII pair<int,int>
#define eps 1e-6
#define inf 1e17
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
int vis[maxn];
int prime[maxn];
int cnt=0;
void gao(){
    for(int i=2;i<maxn;i++){
        if(vis[i]) continue;
        prime[cnt++]=i;
        for(int j=2*i;j<maxn;j+=i){
            vis[j]=1;
        }
    }
}
struct node{
    int x,cnt;
}fac[105];
int main() {
   gao();
   int n;
   int tot=0;
   sca(n);
   printf("%d=",n);
   if(n==1){printf("1");return 0;}
   for(int i=0;i<cnt;i++){
     if(n%prime[i]==0){
        fac[tot].x=prime[i];
        fac[tot].cnt=0;
        while(n%prime[i]==0){
            fac[tot].cnt++;
            n/=prime[i];
        }
        tot++;
     }
     if(n==1)break;
   }
   if(n!=1){
    fac[tot].x=n;
    fac[tot++].cnt=1;
   }

   for(int i=0;i<tot;i++){
    if(i>0)printf("*");
    printf("%d",fac[i].x);
    if(fac[i].cnt>1) printf("^%d",fac[i].cnt);
   }
}