素数计数函数

在数学中，素数计数函数是一个用来表示小于或等于某个实数x的素数的个数的函数，记为$\pi (x)$。

π(n)的最初60个值

历史

在数论中，素数计数函数的增长率引起了很大的兴趣。在18世纪末，高斯和勒让德曾猜想这个函数大约为：

$x/\ln (x)$

也就是

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x)}{x/\ln (x)}=1.$

这就是素数定理。一个等价的表述，是：

$\underset{x\to \mathrm{\infty }}{\lim }\pi (x)/\mathrm{li}(x)=1$

其中$\mathrm{li}(x)$是对数积分函数。这个定理在1896年由法国数学家雅克·阿达马和比利时数学家德·拉·瓦莱布桑先后独立给出证明。证明用到了黎曼ζ函数的性质。

目前已知$\pi (x)$还有更精确的估计，例如：

$\pi (x)=\mathrm{li}(x)+\mathrm{O}(x\exp (-\frac{\sqrt{\ln (x)}}{15}))$

其中O是大O符号。1948年，阿特勒·塞爾伯格和保罗·埃尔德什不使用函数或复分析证明了素数定理。

另外一个关于素数计数函数的增长率的猜想，是：

$\sum _{p\le x}{p}^n\sim \pi (x^{n+1})\sim Li(x^{n+1}).$

π(x)、x / ln x和li(x)

x	Template:Pi(x)	Template:Pi(x) − x / ln x	li(x) − Template:Pi(x)	x / Template:Pi(x)	x / ln x  % Error
10	4	−0.3	2.2	2.500	-7.5%
102	25	3.3	5.1	4.000	13.20%
103	168	23	10	5.952	13.69%
104	1,229	143	17	8.137	11.64%
105	9,592	906	38	10.425	9.45%
106	78,498	6,116	130	12.740	7.79%
107	664,579	44,158	339	15.047	6.64%
108	5,761,455	332,774	754	17.357	5.78%
109	50,847,534	2,592,592	1,701	19.667	5.10%
1010	455,052,511	20,758,029	3,104	21.975	4.56%
1011	4,118,054,813	169,923,159	11,588	24.283	4.13%
1012	37,607,912,018	1,416,705,193	38,263	26.590	3.77%
1013	346,065,536,839	11,992,858,452	108,971	28.896	3.47%
1014	3,204,941,750,802	102,838,308,636	314,890	31.202	3.21%
1015	29,844,570,422,669	891,604,962,452	1,052,619	33.507	2.99%
1016	279,238,341,033,925	7,804,289,844,393	3,214,632	35.812	2.79%
1017	2,623,557,157,654,233	68,883,734,693,281	7,956,589	38.116	2.63%
1018	24,739,954,287,740,860	612,483,070,893,536	21,949,555	40.420	2.48%
1019	234,057,667,276,344,607	5,481,624,169,369,960	99,877,775	42.725	2.34%
1020	2,220,819,602,560,918,840	49,347,193,044,659,701	222,744,644	45.028	2.22%
1021	21,127,269,486,018,731,928	446,579,871,578,168,707	597,394,254	47.332	2.11%
1022	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1,932,355,208	49.636	2.02%
1023	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	7,250,186,216	51.939	1.93%
1024	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	17,146,907,278	54.243	1.84%
1025	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	55,160,980,939	56.546	1.77%
1026	1,699,246,750,872,437,141,327,603	28,883,358,936,853,188,823,261	155,891,678,121	58.850	1.70%
1027	16,352,460,426,841,680,446,427,399	267,479,615,610,131,274,163,365	508,666,658,006	61.153	1.64%

计算π(x)的方法

如果$x$不太大，一个简单的计算$\pi (x)$的方法就是算出每个素数（比如使用埃拉托斯特尼筛法）。

一个比较复杂的计算$\pi (x)$的方法是勒让德发现的：给定$x$，如果$p_1$、 $p_2$、 ……、 $p_k$是不同的素数，则小于$x$且不能被任何一个$p_i$整除的整数个数是：

$\lfloor x\rfloor -\sum _i\lfloor \frac{x}{p_i}\rfloor +\sum _{i<j}\lfloor \frac{x}{p_i{p}_j}\rfloor -\sum _{i<j<k}\lfloor \frac{x}{p_i{p}_j{p}_k}\rfloor +\cdots ,$

（其中$\lfloor \cdot \rfloor$是取整函数）。因此这个数等于：

$\pi (x)-\pi \left(\sqrt{x}\right)+1$

其中$p_1,p_2,\dots ,p_k$是小于或等于$x$的平方根的素数。

恩斯特·梅塞尔在1870年和1885年发表的一系列文章中，描述并使用了一个计算$\pi (x)$的组合方法。设$p_1$, $p_2$, …, $p_n$是最初$n$个素数，將不大于$m$且不被任何$p_i$整除的自然数个数记为$\mathrm{\Phi }(m,n)$，那么：

$\mathrm{\Phi }(m,n)=\mathrm{\Phi }(m,n-1)-\mathrm{\Phi }(\left[\frac{m}{p_n}\right],n-1).$

给定一个自然数$m$，如果$n=\pi \left(\sqrt[3]{m}\right)$且$\mu =\pi \left(\sqrt{m}\right)-n$，那么：

$\pi (m)=\mathrm{\Phi }(m,n)+n(\mu +1)+\frac{{\mu }^2-\mu }{2}-1-\sum _{k=1}^{\mu }\pi \left(\frac{m}{p_{n+k}}\right).$

利用这种方法，梅塞尔计算了$x$等于5×10⁵、10⁶、10⁷以及10⁸时$\pi (x)$的值。

1959年，德里克·亨利·勒梅尔推广并简化了梅塞尔的方法。对于实数$m$和自然数$n$和$k$，定义$P_k(m,n)$为不大于m且正好有k个大于$p_n$的素因子的整数个数。更进一步，设定$P_0(m,n)=1$。那么：

$\mathrm{\Phi }(m,n)=\sum _{k=0}^{+\mathrm{\infty }}{P}_k(m,n),$

这个和实际上只有有限个非零的项。设$y$为一个整数，使得$\sqrt[3]{m}\le y\le \sqrt{m}$，并设$n=\pi (y)$。那么当$k$ ≥ 3时，$P_1(m,n)=\pi (m)-n$且$P_k(m,n)=0$。因此：

$\pi (m)=\mathrm{\Phi }(m,n)+n-1-P_2(m,n).$

$P_2(m,n)$的计算可以用这种方法来获得：

$P_2(m,n)=\sum _{y<p\le \sqrt{m}}(\pi \left(\frac{m}{p}\right)-\pi (p)+1).$

另一方面，$\mathrm{\Phi }(m,n)$的计算可以用以下规则来完成：

1. $\mathrm{\Phi }(m,0)=\lfloor m\rfloor ;$
2. $\mathrm{\Phi }(m,b)=\mathrm{\Phi }(m,b-1)-\mathrm{\Phi }(\frac{m}{p_b},b-1).$

利用这种方法，勒梅尔计算了$\pi \left(10^{10}\right)$。

其它素数计数函数

我们也使用其它的素数计数函数，因为它们更方便。其中一个是黎曼的素数计数函数，通常记为${\mathrm{\Pi }}_0(x)$。这个函数在自变量为素数的幂pⁿ时突然增加了1/n，而该点的值则是两边的平均值。我们可以用以下公式来定义${\mathrm{\Pi }}_0(x)$：

${\mathrm{\Pi }}_0(x)=\frac{1}{2}(\sum _{p^n<x}\frac{1}{n}+\sum _{p^n\le x}\frac{1}{n})$

其中p是素数。

也可以写成以下公式：

${\mathrm{\Pi }}_0(x)=\sum _2^x\frac{\mathrm{\Lambda }(n)}{\ln n}-\frac{1}{2}\frac{\mathrm{\Lambda }(x)}{\ln x}=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n}{\pi }_0(x^{1/n})$

其中Λ(n)是馮·曼戈爾特函數，

${\pi }_0(x)=\underset{\epsilon \to 0}{\lim }\frac{\pi (x-\epsilon )+\pi (x+\epsilon )}{2}.$

利用默比乌斯反演公式，可得：

${\pi }_0(x)=\sum _{n=1}^{\mathrm{\infty }}\frac{\mu (n)}{n}{\mathrm{\Pi }}_0(x^{1/n})$

知道了黎曼ζ函数的对数与馮·曼戈爾特函數$\mathrm{\Lambda }$之间的关系，并利用佩龙公式，可得：

$\ln \zeta (s)=s\underset{0}{\overset{\mathrm{\infty }}{\int }}{\mathrm{\Pi }}_0(x)x^{-s+1}dx$

不等式

下面是一些有用的π(x)不等式。

$\frac{x}{\ln x}<\pi (x)<1.25506\frac{x}{\ln x}$，左不等式适用于x ≥ 17，右不等式适用于x>1，常数1.25506为 $\frac{30\ln 113}{113}$保留5位有效小数，$\frac{\pi (x)\ln x}{x}$最大值为x = 113。

Pierre Dusart 在2010年证明：

$\frac{x}{\ln x-1}<\pi (x)$ （其中$x\ge 5393$）

$\pi (x)<\frac{x}{\ln x-1.1}$ （其中$x\ge 60184$）

第n个素数p_n的不等式：

$n\ln n+n\ln \ln n-n<p_n<n\ln n+n\ln \ln n$

左面的不等式当n ≥ 2时成立，右面的不等式当n ≥ 6时成立，上限由Rosser（1941）提出，下限由Dusrat（1999）提出。

第n个素数的一个估计是：

$p_n=n\ln n+n\ln \ln n-n+\frac{n\ln \ln n-2n}{\ln n}+O\left(\frac{n(\ln \ln n{)}^2}{(\ln n{)}^2}\right).$

参考文献

• Template:Cite book

• Marc Deléglise and Jöel Rivat, Computing $\pi (x)$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko methodTemplate:Wayback, Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245

• Template:Cite book

• Template:Cite book

• Template:MathWorld

• Hwang H. Cheng Prime Magic conference given at the University of Bordeaux (France) at year 2001 Démarches de la Géométrie et des Nombres de l'Université du Bordeaux

• Titchmarsh, E. C. The Theory of Functions, 2nd ed. Oxford, England: Oxford University Press, 1960.

• Oliveira e Silva, Tomás Tables of values of pi(x) and of pi2(x) Template:Wayback

• Gourdon, Xavier; Sebah,Pascal PrimePi values thru 4E22Template:Wayback