问题

\[ 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}
\]