唯一分解定理

定义

每个大于$1$的自然数, 要么本身就是质数, 要么可写为$2$个或以上质数积, 且质因子排列顺序唯一

• $N = \prod_{i=1}^k p_i^{a_i}$ ($p_1< p_2 < …< p_k<N$且均为质数)

例, $6936=2^3317^2, 1200=2^435^2$

• 若 $N = \prod_{i=1}^k p_i^{a_i}$, 其因数有 $\prod_{i=1}^{k} (a_i+1)$ 个

证明

对于$p_1$部分来说, 分以下情况,

• 包含$0$个$p_1$时, $N$ 的因数$x_1 = p_2^{a_2}\cdots p_k^{a_k}$

• 包含$1$个$p_1$时, $N$ 的因数$x_2 = p_1^{1}p_2^{a_2}\cdots p_k^{a_k}$

$\cdots$

• 包含$a_1$个$p_1$时, $N$ 的因数$x_{a_1} = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

$p_1$部分总因数个数为$(a_1 + 1)$,

$p_2$部分总因数个数为$(a_2 + 1)$

$\cdots$

$p_i$部分总因数个数为$(a_i + 1)$

• $N$的因数个数为 $\prod_{i=1}^{k} (a_i + 1)$

例, $24 = 2 ^ 3 * 3 ^ 1$, 因数有$(3 + 1) * (1 + 1) = 8个$

求100!因数个数

#include<stdio.h>

typedef long long ll;

const int n = 100;

int main(void){
    int b[101] = {0};
    int x;
    for (int i = 1; i <= n; i++) {
        x = i;
        for (int j = 2; j * j <= x; j++) {
            // 当j是x的素因子时
            while (x % j == 0) {
                // m[j]表示素因子j的指数
                b[j]++;
                x /= j;
            }
        }
        // 若x不为1说明其为素数
        if (x != 1) {
            b[x]++;
        }
    }

    ll sum = 1;
    for(int i = 1;i <= n ;i++){
        if(b[i]){
            sum *= b[i];
        }
    }
    printf("%lld\n", sum);
    return 0;
}