Legendre’s Formula 勒让德公式

Legendre’s Formula calculates the exponent of a prime p in the prime factorization of factorial \(n!\).

For positive integer n and prime p:

\(v_p(n!)=\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^k} \right\rfloor\)

The floor function \(\lfloor x\rfloor\) means the greatest integer less than or equal to x. The summation terminates when \(p^k>n\).

中文释义

勒让德公式：用来求解正整数阶乘 \(n!\) 的素因数分解里，素数 p 出现的最高幂次。

公式：

\(v_p(n!)=\left\lfloor \frac{n}{p} \right\rfloor+\left\lfloor \frac{n}{p^2} \right\rfloor+\left\lfloor \frac{n}{p^3} \right\rfloor+\dots\)

\(\lfloor x\rfloor\) 为向下取整；当 \(p^k>n\) 时，该项数值为 0，计算自动停止。

核心原理

每 p 个数出现 1 个 p 的倍数，贡献 1 个素因子p；

每 \(p^2\) 个数出现 1 个平方倍数，额外再多贡献 1 个p；

更高次幂同理，累加得到总次数。

例 1 基础求阶乘素因子次数

Problem: Find the exponent of prime 2 in \(10!\)

题目：求 \(10!\) 中素因子 2 的次数

\(\begin{align*} v_2(10!)&=\left\lfloor\frac{10}{2}\right\rfloor+\left\lfloor\frac{10}{4}\right\rfloor+\left\lfloor\frac{10}{8}\right\rfloor+\left\lfloor\frac{10}{16}\right\rfloor\\ &=5+2+1+0=\boldsymbol{8} \end{align*}\)

例 2 换素数计算

Problem: Calculate \(v_3(15!)\)

题目：计算 \(15!\) 里素因子 3 的次数

\(v_3(15!)=\left\lfloor\frac{15}{3}\right\rfloor+\left\lfloor\frac{15}{9}\right\rfloor=5+1=\boldsymbol{6}\)

例 3 经典应用：求阶乘末尾连续 0 的个数

末尾 0 由 \(2\times5\) 成对产生，取 2、5 幂次的较小值。

Problem: How many trailing zeros does \(25!\) have?

题目：求 \(25!\) 末尾有多少个连续的 0

\(\begin{align*} v_5(25!)&=\left\lfloor\frac{25}{5}\right\rfloor+\left\lfloor\frac{25}{25}\right\rfloor=5+1=6\\ v_2(25!)&=12+6+3+1=22 \end{align*}\)

取最小值，末尾共有 \(\boldsymbol{6}\) 个 0。

例 6 写出阶乘标准素因数分解

题目：写出 \(6!\) 的素因子分解式

• \(v_2(6!)=\lfloor6/2\rfloor+\lfloor6/4\rfloor+\lfloor6/8\rfloor=3+1=4\)
• \(v_3(6!)=\lfloor6/3\rfloor=2\)
• \(v_5(6!)=\lfloor6/5\rfloor=1\)

\(6! = 2^4 \times 3^2 \times 5^1\)

例 7 高阶竞赛：最大整数 t 满足 \(7^t \mid 100!\)

\(v_7(100!)=\left\lfloor\frac{100}{7}\right\rfloor+\left\lfloor\frac{100}{49}\right\rfloor+\left\lfloor\frac{100}{343}\right\rfloor=14+2=16\)