$n!$ 的标准分解式
\[ n!=\prod_{\text{prime}\ p\leqslant n}p^{\sum_{r=1}^{+\infty}[\frac{n}{p^r}]} \]
于是
\[
v_p(n!)=\sum_{k\geqslant 1}\lfloor\frac{n}{p^k}\rfloor,\quad n\geqslant 1.
\]
这里 $v_p(m)$ 指正整数 $m$ 作素因子分解后, 其中素因子 $p$ 的幂次. 称之为 $p$ 进赋值.
推论: 对任意素数 $p$, 有
\[
\frac{n}{p}-1 < v_p(n!)\leqslant\frac{n}{p}+\frac{n}{p(p-1)}\quad (n\geqslant 1).
\]
References:
G. 特伦鲍姆(Gérald Tenenbaum) 著, 《解析与概率数论导引》, 陈华一 译.
Remark:
这个公式可以应用于 $n!$ 的快速计算.
算法:
1. 将 $n$ 分解质因数. $n=p_{1}^{i_1}p_{2}^{i_2}\cdots p_{m}^{i_m}$.
2. 对于 $p_k$, 计算 $d_r:=\lfloor\frac{n}{p_k^r}\rfloor$, 直到 $n < p_k^r$.
3. 求和 $s_k:=d_1+d_2+\cdots+d_r+\cdots$ . 注意这是一个有限和. 当 $n < p_k^r$ 时, $d_r=0$.
4. 最后得到 $n!$
\[
n!=p_1^{s_1}p_2^{s_2}\cdots p_m^{s_m}
\]