算术基本定理的内容

我们知道任何一个大于 $1$ 的正整数 $n$ 都可以表示成素数之积,即 $n=p_1p_2\cdots p_m$,其中 $p_i(1\leqslant i\leqslant m)$ 是素数。下面就是算数基本定理的一个重要结果,它说明了任何一个大于 $1$ 正整数,都可以由一系列素数相乘得来。

每个大于 $1$ 的正整数 $n$ 都可以被唯一地写成素数的乘积,在乘积中的素因子按照非降序排列。正整数 $n$ 的分解式 $n=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ 称为 $n$ 的标准分解式,其中 $p_1,p_2,\cdots,p_k$ 是素数,$p_1\lt p_2\lt \cdots\lt p_k$,且 $\alpha_1,\alpha_2,\cdots,\alpha_k$ 是正整数。

一些性质:
(1) 若 $n​$ 的标准素因子分解表达式为 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}​$,设 $d(n)​$ 为 $n​$ 的正因子的个数,$\phi(n)​$ 为 $n​$ 的所有因子之和,则有
$d(n)=(\alpha_1+1)\cdot(\alpha_2+1)\cdot\cdots\cdot(\alpha_k+1)​$
$\phi(n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\cdots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}​$

(2) 设 $a=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k},b=p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}$,则有
$gcd(a,b)=p_1^{min(\alpha_1,\beta_1)}\cdot p_2^{min(\alpha_2,\beta_2)}\cdot\cdots\cdot p_k^{min(\alpha_k,\beta_k)}$
$lcm(a,b)=p_1^{max(\alpha_1,\beta_1)}\cdot p_2^{max(\alpha_2,\beta_2)}\cdot\cdots\cdot p_k^{max(\alpha_k,\beta_k)}$

(3) 如果 $a$ 和 $b$ 为实数,则
$max(gcd(a,b))+min(gcd(a,b))=a+b$

(4) 如果 $a$ 和 $b$ 是正整数,则
$lcm(a,b)=\frac{ab}{gcd(a,b)}$

(5) $n!$ 的素因子分解中的素数 $p$ 的幂为
$[\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^3}]+\cdots$

算术基本定理的应用:
上面说了什么是算术基本定理,也给出了一些性质,但是具体这些性质该怎么用呢?举个简单的例子吧:
例 (1) 计算 $N!$ 末尾 $0$ 的个数。
LeetCode 172 - Factorial Trailing Zeroes