深入探讨数论中的基石理论，从质数幂次的精确计算到勒让德猜想的深远影响。本文为您提供详尽的数学推导、历史背景及现代应用场景。
在数论领域，勒让德定理（Legendre's Theorem）通常指代两个紧密相关但有所区别的重要结论。最为人熟知的是关于阶乘质因数分解的勒让德公式，它揭示了如何精确计算任意正整数 n! 中包含某个质数 p 的最高次幂。此外，阿德里安 - 马里·勒让德（Adrien-Marie Legendre）在质数分布领域的早期工作，特别是勒让德猜想，也是现代解析数论发展的关键转折点。
设 p 是一个质数，n 是一个正整数。则 n! 的质因数分解中，质数 p 的指数 E_p(n!) 由以下公式给出：
E_p(n!) = sum_{k=1}^{infty} leftlfloor frac{n}{p^k}
ight
floor = leftlfloor frac{n}{p}
ight
floor + leftlfloor frac{n}{p^2}
ight
floor + leftlfloor frac{n}{p^3}
ight
floor + cdots其中 lfloor x floor 表示不大于 x 的最大整数（向下取整）。由于当 p^k > n 时，lfloor n/p^k floor = 0，该级数实际上是有限的。
这个公式的直观理解是：在 1 到 n 的所有整数中，有 lfloor n/p floor 个数能被 p 整除（贡献至少一个因子 p），有 lfloor n/p^2 floor 个数能被 p^2 整除（额外贡献一个因子 p），以此类推。将所有贡献相加，即得到总指数。
我们要计算 E_3(100!)。根据勒让德公式：
总和：33 + 11 + 3 + 1 = 48。
这意味着 100! 可以被 3^{48} 整除，但不能被 3^{49} 整除。
这是一个典型的竞赛或编程题目场景。我们逐步计算：
结果：289 + 41 + 5 = 335。
勒让德公式的证明基于简单的计数原理。考虑集合 {1, 2, ..., n}：
将所有这些贡献累加，即为总指数。证毕。
法国数学家阿德里安 - 马里·勒让德在他的著作《数论尝试》（Essai sur la théorie des nombres）中首次提出了关于质数分布的猜想。他观察到质数的密度似乎随着数字增大而降低，并给出了一个著名的近似公式：
π(x) ≈ x / (ln x - 1.08366)。虽然这个常数后来被证明不如高斯的对数积分 Li(x) 精确，但在当时是巨大的突破。
勒让德提出了一个更为具体的断言：对于任何整数 n > 1，在区间 (n, 2n) 之间至少存在一个质数。这就是著名的勒让德猜想。
俄罗斯数学家帕夫努季·切比雪夫（Pafnuty Chebyshev）成功证明了勒让德猜想。为了纪念这一成就，该定理现在常被称为伯特兰 - 切比雪夫定理（Bertrand-Chebyshev Theorem）。切比雪夫利用勒让德定理（关于阶乘质因数分解的公式）作为核心工具，通过估计 (2n)! / (n!n!) 的质因数性质，完成了这一壮举。
匈牙利天才数学家保罗·埃尔德什（Paul Erdős）在 19 岁时给出了该定理的一个极其优美且初等的证明，完全避开了复杂的解析工具，仅利用了勒让德公式和二项式系数的性质。
以下是一个高效的 Python 函数，用于计算 n! 中质数 p 的指数，完美复现勒让德定理的逻辑。
def legendre_formula(n, p):
"""
计算 n! 中质数 p 的指数
:param n: 正整数
:param p: 质数
:return: p 的指数
"""
count = 0
while n >= p:
count += n // p
n //= p
return count
测试用例
if __name__ == "__main__":
print(f"100! 中 3 的指数: {legendre_formula(100, 3)}") # 输出 48
print(f"2024! 中 7 的指数: {legendre_formula(2024, 7)}") # 输出 335
print(f"1000! 中 2 的指数: {legendre_formula(1000, 2)}") # 输出 994