素数计数函数

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

<image>

## 历史

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

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

也就是

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

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

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

其中$\operatorname{li}(x)$是对数积分函数。

帕夫努季·切比雪夫曾在1852年证明了以下和质数计数函数$\pi(n)$相关的不等式：

对于足够大的$x$，有$A\frac{x}{\ln(x)} < \pi(x) < \frac{6A}{5}\frac{x}{\ln(x)} \; \text{，其中} \; A \approx 0.92129.$

作为此定理的引申结果，他也证明了伯特兰-切比雪夫定理；而在证明这不等式的过程中，他也引进了切比雪夫函数。

这个定理在1896年由法国数学家雅克·阿达马和比利时数学家德·拉·瓦莱布桑先后独立给出证明。证明用到了黎曼ζ函数的性质。

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

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

其中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｜Π(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)的方法

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

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

$$\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\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$整除的自然数个数记为$\Phi(m,n)$，那么：

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

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

$$\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).\,$$

利用这种方法，梅塞尔计算了$x$等于5×105、106、107以及108时$\pi(x)$的值。

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

$$\Phi(m,n)=\sum_{k=0}^{+\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)=\Phi(m,n)+n-1-P_2(m,n).$$

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

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

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

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

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

## 其它素数计数函数

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

$$\Pi_0(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)$$

其中p是素数。

也可以写成以下公式：

$$\Pi_0(x) = \sum_2^x \frac{\Lambda(n)}{\ln n} - \frac12 \frac{\Lambda(x)}{\ln x} = \sum_{n=1}^\infty \frac1n \pi_0(x^{1/n})$$

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

$$\pi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2.$$

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

$$\pi_{0}(x) = \sum_{n=1}^\infty \frac{\mu(n)}n \Pi_0(x^{1/n})$$

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

$$\ln \zeta(s) = s \int_0^\infty \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个素数pn的不等式：

$$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).$$

## 参考文献

- Marc Deléglise and Jöel Rivat, Computing $\pi(x)$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method, Mathematics of Computation, vol. 65, number 33, January 1996, pages 235–245
- 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