唯一分解定理

百度百科：
在这里插入图片描述

一个数n肯定能被分解成 n=p1^a1^ * p2^a2^ . . .*pn^an^
模板

int prime_fac[N],cnt=0,sum;
int prime_index[N];
void fact(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            cnt++;
            prime_fac[cnt]=i;
            prime_index[cnt]=0;
        }
        while(n%i==0){
            n/=i;
            prime_index[cnt]++;
            sum++;
        }
    }
    if(n!=1){
        cnt++;
        prime_fac[cnt]=n;//底数 
        prime_index[cnt]=1;//指数
         sum++;
    }
}

prime_fac[cnt]存放的底数，都是质数
prime_index[cnt]存放的指数，也就是每个对数对应的指数