# 素数计数函数

π(n)的最初60个值

## 历史

$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\!$

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

$\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)
10 4 −0.3 2.2 2.500
102 25 3.3 5.1 4.000
103 168 23 10 5.952
104 1,229 143 17 8.137
105 9,592 906 38 10.425
106 78,498 6,116 130 12.740
107 664,579 44,158 339 15.047
108 5,761,455 332,774 754 17.357
109 50,847,534 2,592,592 1,701 19.667
1010 455,052,511 20,758,029 3,104 21.975
1011 4,118,054,813 169,923,159 11,588 24.283
1012 37,607,912,018 1,416,705,193 38,263 26.590
1013 346,065,536,839 11,992,858,452 108,971 28.896
1014 3,204,941,750,802 102,838,308,636 314,890 31.202
1015 29,844,570,422,669 891,604,962,452 1,052,619 33.507
1016 279,238,341,033,925 7,804,289,844,393 3,214,632 35.812
1017 2,623,557,157,654,233 68,883,734,693,281 7,956,589 38.116
1018 24,739,954,287,740,860 612,483,070,893,536 21,949,555 40.420
1019 234,057,667,276,344,607 5,481,624,169,369,960 99,877,775 42.725
1020 2,220,819,602,560,918,840 49,347,193,044,659,701 222,744,644 45.028
1021 21,127,269,486,018,731,928 446,579,871,578,168,707 597,394,254 47.332
1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1,932,355,208 49.636
1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 7,250,186,216 51.939

## 计算π(x)的方法

$\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i

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

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

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

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

1959年，德里克·亨利·勒梅尔Derrick Henry Lehmer）推广并简化了梅塞尔的方法。对于实数$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),\,$

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

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

$P_2(m,n)=\sum_{y

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

## 其它素数计数函数

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

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

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

$\ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s+1}\,dx$

## 不等式

$\pi(x) < 1.25506 \frac {x} {\log x} \!$，x > 1。
$\frac {x} {\log x + 2} < \pi(x) < \frac {x} {\log x - 4} \!$，x ≥ 55。

$n\ \ln n + n\ln\ln n - n < p_n < n \ln n + n \ln \ln n \!$n ≥ 6。

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

## 参考文献

• Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory. MIT Press. 1996: volume 1 page 234 section 8.8. ISBN 0-262-02405-5.
• 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.
• 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.