偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。
这个证明不仅帅气，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。
假设我们从所有不超过 n 的自然数中随机选取一个数 N ，并把它分解成质因数的乘积 N = P1^X1* P2^X2 * … * Pm^Xm，其中 m 是不超过 n 的素数的个数。
注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立，因此我们有 Xi ≤ log(n) 。
真正帅的地方来了。
考虑随机选取一个 N 带来的信息熵，我们有：
log(n) = H(N)
= H(X1, X2, …, Xm)
≤ H(X1) + H(X2) + … + H(Xm)
≤ log(log(n)+1) * m
上面的第一个等号是由信息熵的定义直接得出的。
第二个等号是由唯一分解定理得到的：
由于一个数可以唯一地分解为质因数的乘积，因此 N 和 (X1, X2, …, Xm) 是一一对应的，知道了前者也就确定了后者，它们的信息熵是相同的。
第三行的不等式是由于我们放开了 Xi 的取值条件（每个 Xi 独立取值可能会导致它们的乘积超过 n ），必然会增加结果的不确定性。
而每个 Xi 的取值范围不会超出 0 到 log(n) ，最多 log(n)+1 种情况，因此 H(Xi ) ≤ log(log(n)+1) ，这就得到了第四行的那个不等式。
整理上式，我们得到了 m ≥ log(n) / log(log(n)+1) ，这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的，还给出了不超过 n 的素数个数的一个下界。
来源：
http://www.matrix67.com/blog/archives/2700
发表于 2018-7-18 05:08
收藏
分享