本文将略述数论中的欧拉函数的推广与素数分布的关系。
设x是给定的自然数，p_i是其素因数，n是x中素因数的个数。欧拉函数ψ(x)表示小于x并且与x互素的自然数的个数。则有：
例如，若x=30，由于30的素因数为2、3、5，则有ψ(30)＝30·(1－1/2)(1－1/3)(1－1/5)＝8。其中1，7，11，13，17，19，23，29与30互素。
如果我们想计算不大于30的素数个数，是否也可利用类似欧拉函数的思路呢？
我们不妨将p_i与n重新定义。将p_i定义为不大于√30的素数，刚好也是2，3，5；将n定义为不大于√30的素数个数，则n＝3。
于是30以内不能为2，3，5整除的数的个数为ψ(30)＝30·(1－1/2)(1－1/3)(1－1/5)＝8。而这其中，除了自然数1以外其他7个数必然是素数。因此30以内的素数个数是：
ψ(30)＋n－1＝8＋3－1＝10。
如果π(x)表示不大于x的素数的个数，p_i表示不大于√x的素数，n表示不大于√x的素数的个数，ψ(x)表示不大于x且不能为所有不大于√x的素数整除的个数，于是必有：
π(x)～ψ(x)＋n－1
注意，这里的ψ(x)已经不是欧拉函数，而是欧拉函数的推广形式。
我们知道，根据素数定理有π(x)～x/ln x。那么ψ(x)＋n－1与x/ln x是什么关系呢？
事实上，ψ(x)＋n－1～x/ln x，并且ψ(x)＋n－1≥x/ln x。
不妨以x=1000为例。根据π(x)～x/ln x，则有π(1000)～1000/ln 1000≈144。估算出来1000以内的素数多于144个。
我们再根据π(x)～ψ(x)＋n－1来进行计算。不大于√1000的素数为2，3，5，7，11，13，17，19，23，29，31，因而n＝11
于是：
π(1000)～ψ(1000)＋11－1
＝1000·1/2·2/3·4/5·6/7·10/11·12/13·16/17·
18/19·22/23·28/29·30/31＋10
＝1000·13271040/86822723＋10
≈152＋10＝162
1000以内的素数实际有168个，显然用π(x)～ψ(x)＋n－1比用π(x)～x/ln x计算繁琐得多，但是精确度提高了不少。
这一新的素数分布公式π(x)～ψ(x)＋n－1的更大价值其实在于用于证明而不是计算。我们可以很方便地用之于证明贝特朗定理，也即证明：在自然数x～2x之间必有素数存在。
此时令p_i表示不大于√2x的所有素数，令n表示不大于√2x的所有素数的个数，标记S为x～2x之间的素数个数。
于是必有：
S～ψ(2x)/2
＝x·1/2·2/3·4/5·……·(p_n－1)/p_n
＞x/p_n
＞1
由此可见，在自然数x～2x之间必有素数存在。命题得证。
上述方法的进一步推广，可用之于哥德巴赫猜想、孪生素数猜想、波利尼亚克猜想以及格林-陶定理的证明。
閱讀更多 建章看世界 的文章
