孪生素数,素数无穷多个的证明

孪生素数

        只有1和本身即只能被自身和1整除的正整数叫做素数。孪生素数是指两个相差为2的素数，例如3和5，17和19。        素数在自然数的分布具有一定的规律，随着数量的不断增大，素数的密度则会越来越小，比如100以内的素数所占比例为25%，而100万以内的素数所占比例只有7.85%，且随着数量级的不断增大，两个相邻素数之间的平均差值越来越大。从其分布的规律就可看出孪生素数猜想的奇妙，倘若相邻素数之间的差值真的越来越大，那么出现无穷对孪生素数就不是那么显然的事了。

素数无穷多个的证明

这个证明不仅帅气，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。

假设我们从所有不超过 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 的素数个数的一个下界。