唯一分解定理:
任意一个正整数,都可以分成有限个素数的乘积形式
没错,这就是核心,短叭?

例如:48 = 2 * 2 * 2 * 2 * 3,54 = 2 * 3 * 3 * 3。

唯一分解定理推论:
根据分解过后的质因子种类及其个数能推出这个数有多少个因子
如:上述48 = 2 * 2 * 2 * 2 * 3 = 2^4 * 3^1
其因子数就为(4+1) * (1+1) 就是根据组合数学来推的,2的个数有0 -到 4种选法,3的个数有 0 到 1种选法
54 = 2^1 * 3^3
因子数为:(1+1) * (3+1)

代码实现把一个数分解成若干素数的乘积形式:
模板:

void weiyi(int n){
    int cnt=0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            p[++cnt]=i,e[cnt]=0;
            while(n%i==0){
                n/=i;
                e[cnt]++;
            }
        }
    }
    if(n>1) p[++cnt]=n,e[cnt]=1;
}

Logo

Agent 垂直技术社区,欢迎活跃、内容共建。

更多推荐