利用阶乘因子数公式证明素数无穷多

搞过 OI/ACM 的同学们想必对一道经典题目印象极深：求 n 的阶乘末尾有多少个 0 。注意到末尾的一个 0 是由一个因子 2 和一个因子 5 相乘产生的；但在 n 的阶乘里，因子 5 的个数通常远远少于因子 2 。因此这个问题就等价于问 n 的阶乘里有多少个因子 5 。在 n 的阶乘式中，每个 5 的倍数里都含有一个因子 5 ，每个 25 的倍数里都还含有另外一个因子 5 ，每个 125 的倍数里都还有第三个因子 5 ……因此， n 的阶乘里因子 5 的个数的计算公式就是 ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + … 。如果把 K 的阶乘里素因子 p 的个数记作 Φ(p, K) ，则 Φ(p, K) = Σ⌊K/(p^i)⌋ 。有意思的是，最近 The American Mathematical Monthly 上的一篇文章利用这个公式瞬间证明了素数无穷多的定理。

如果素数是有限的，则 K 的阶乘就可以写成所有 p^Φ(p, K) 的乘积，其中的 p 取遍所有的素数。注意到 Φ(p, K) = Σ⌊K/(p^i)⌋ < Σ(K/(p^i)) = K/(p-1) < K ，因此对任意正整数 K 都有 K! < (Πp)^K ，其中 Πp 表示所有素数的乘积。但当 K 充分大的时候， K! 显然会超过一个常数的 K 次方，矛盾。因此素数不可能是有限的。 来源：http://www.cut-the-knot.org/wiki-math(http://www.cut-the-knot.org/wiki-math/index.php?n=Arithmetic.InfinitudeOfPrimesFromLegendresFormula)