素数计数函数

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

π(n)的最初60个值

历史

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

${\displaystyle x/\operatorname {ln} (x)\!}$

也就是

${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\operatorname {ln} (x)}}=1.\!}$

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

${\displaystyle \lim _{x\rightarrow \infty }\pi (x)/\operatorname {li} (x)=1\!}$

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

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

${\displaystyle \pi (x)=\operatorname {li} (x)+\mathrm {O} \left(x\exp \left(-{\frac {\sqrt {\ln(x)}}{15}}\right)\right)\!}$

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

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

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

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

x	π(x)	π(x) − x / ln x	li(x) − π(x)	x / π(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)的方法

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

一个比较复杂的计算${\displaystyle \pi (x)}$的方法是勒让德发现的：给定${\displaystyle x}$，如果${\displaystyle p_{1}}$、 ${\displaystyle p_{2}}$、 ……、 ${\displaystyle p_{k}}$是不同的素数，则小于${\displaystyle x}$且不能被任何一个${\displaystyle p_{i}}$整除的整数个数是：

${\displaystyle \lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots ,}$

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

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

其中${\displaystyle p_{1},p_{2},\dots ,p_{k}}$是小于或等于${\displaystyle x}$的平方根的素数。

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

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

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

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

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

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

${\displaystyle \Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n),\,}$

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

${\displaystyle \pi (m)=\Phi (m,n)+n-1-P_{2}(m,n).}$

${\displaystyle P_{2}(m,n)}$的计算可以用这种方法来获得：

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

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

1. ${\displaystyle \Phi (m,0)=\lfloor m\rfloor ;\,}$
2. ${\displaystyle \Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right).\,}$

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

其它素数计数函数

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

${\displaystyle \Pi _{0}(x)={\frac {1}{2}}{\bigg (}\sum _{p^{n}<x}{\frac {1}{n}}\ +\sum _{p^{n}\leq x}{\frac {1}{n}}{\bigg )}}$

其中p是素数。

也可以写成以下公式：

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

其中Λ(n)是冯·曼戈尔特函数，

${\displaystyle \pi _{0}(x)=\lim _{\varepsilon \rightarrow 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.}$

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

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

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

${\displaystyle \ln \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s+1}\,dx}$

不等式

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

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

Pierre Dusart 在2010年证明：

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

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

第n个素数p_n的不等式：

${\displaystyle 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个素数的一个估计是：

${\displaystyle 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).}$

参考文献

• Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory. MIT Press. 1996: volume 1 page 234 section 8.8. ISBN 0-262-02405-5. 引文使用过时参数coauthors (帮助)

• Marc Deléglise and Jöel Rivat, Computing ${\displaystyle \pi (x)}$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method（页面存档备份，存于互联网档案馆）, Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245

• Dickson, Leonard Eugene. History of the Theory of Numbers I: Divisibility and Primality. Dover Publications. 2005. ISBN 0-486-44232-2.

• Ireland, Kenneth; Rosen, Michael. A Classical Introduction to Modern Number Theory Second edition. Springer. 1998. ISBN 0-387-97329-X. 引文使用过时参数coauthors (帮助) 引文格式1维护：冗余文本 (link)

• 埃里克·韦斯坦因. Riemann Prime Counting Function. 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) （页面存档备份，存于互联网档案馆）

• Gourdon, Xavier; Sebah,Pascal PrimePi values thru 4E22（页面存档备份，存于互联网档案馆）