唯一分解定理入门(转载)

转载至添加链接描述

唯一分解定理：每一个大于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;
}