[数据结构与算法]唯一分解定理

任何一个大于1的自然数?N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1^a1*P2^a2*P3^a3......Pn^an，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。

C++代码实现：
?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 10000001
bool number[maxn+5];
ll prime[maxn/10];
ll len=0;

//欧拉素数筛
void isprime()
{
    memset(number,true,sizeof(number));
    number[0]=false;number[1]=false;
    for(int i=2;i<=maxn;i++)
    {
        if(number[i]) prime[len++]=i;
        for(int j=0;j<len;j++)
        {
            if((i*prime[j])>maxn) break;
            else
            {
                number[i*prime[j]]=false;
                if(i%prime[j]==0) break;
            }
        }
    }
}
int factor[10000];//记录幂指数是多少
int cas=0;
void geta(ll n) //算幂指数是多少
{
    memset(factor,0,sizeof(factor));

    for(int i=0;i<len&&prime[i]*prime[i]<=n;i++)
    {
        while(n%prime[i]==0) //从小到大依次把素因子除去
        {
            factor[cas]++;
            n/=prime[i];
        }
        if(factor[cas]) cas++;
    }
    if(n>1) factor[cas++]=1;
    //prime[i]*prime[i]<=n 当n不满足这个条件的时候
    //应当还有一个素数的一次方(可以想一下10=2*5 但是25已经超过10)
}
int p[100001];int cnt=0;
void getp(ll q) //筛出唯一分解定理的底数
{
    int x=q;
    for(int i=2;(ll)i*i<=q;i++)
    {
        if((x%i)==0)
        {
            p[cnt++]=i;
            while((x%i)==0)
                x/=i;
        }
    }
    if(x>1){
      p[cnt++]=x;
      x=1;
    }//如果最后x大于1，即最后产生了一个小的素数，直接保存即可
}

signed main()
{
    isprime();
    ll n;cin>>n;
    geta(n);
    getp(n);
    for(int i=0;i<cas;i++)
        cout<<factor[i]<<" ";
    cout<<endl;
    for(int j=0;j<cnt;j++)
        cout<<p[j]<<" ";
    return 0;
}