唯一分解定理入門(轉載)

轉載至添加連結描述

唯一分解定理：每一個大于1的正整數均可分解為有限個素數的積，如果不計素因數在乘積中的次序，則分解方式是唯一的。将n的素因數分解中相同的素因子收集到一起，可隻每個大于1的正整數n可唯一地寫成 n = p1a1p2a2p3a3…pkak，其中，p1，p2，p3，…，pk ，是互不相同的素數，而a1，a2，a3，…，ak 是正整數，上面的分解式稱為n的标準分解。

性質：n的正約數個數，τ(n) = (1+a1)(1+a2)(1+a3)…(1+ak) ；n的正約數之和，σ(n)=(1+p1+…+p1a1)(1+p2+…+p2a2)…(1+pk+…+pkak)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5;
bool is[maxn];
int cnt=0;
ll a[maxn];//存素數
ll ds[maxn],zs[maxn];//ds是底數,zs是指數
void init()//打表,歐拉篩
{
    memset(is,true,sizeof(is));
    is[0]=is[1]=false;
    for(int i=2;i<maxn;i++)
    {
        if(is[i]) a[cnt++]=i;
        for(int j=0; i*a[j]<maxn&&j<cnt; j++)
        {
            is[i*a[j]]=false;
            if( i%a[j]==0 ) break;
        }
    }
}
ll fj(ll x)//不同素數的個數
{
    ll k=0,flag=0;
    for(ll i=0; i<cnt; i++ )
    {
        while(x%a[i]==0)
        {
            if(flag==0)
            {
                flag=1;
                k++;
            }
            x/=a[i];
            ds[k]=a[i];
            zs[k]++;
        }
        if(x==1) break;
        flag=0;
    }
    if( x!=1 )//如果分解完x都不等于1,那麼x必定是一個素數
    {
        k++;
        ds[k]=x;
        zs[k]=1;
    }
    return k;
}
int main()
{
    init();
    ll x;
    cin>>x;
    ll k=fj(x);
    for(ll i=1;i<=k;i++) printf("%lld^%lld%c",ds[i],zs[i],i==k?'\n':'*');
    return 0;
}