查看“︁素数计数函数”︁的源代码

{{noteTA|T=zh:素数计数函数;zh-cn:素数计数函数;zh-tw:質數計算函數;zh-hk:質數計算函數;|1=zh:素数;zh-cn:素数;zh-tw:質數;zh-hk:質數;|G1=Math}}

在[[数学]]中，'''素数计数函数'''是一个用来表示小于或等于某个[[实数]]''x''的[[素数]]的个数的[[函数]]，记为<math>\pi(x)</math>。

[[File:PrimePi.svg|thumb|right|400px|π(''n'')的最初60个值]]

==历史==

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

:<math> x/\operatorname{ln}(x)\!</math>

也就是

:<math>\lim_{x\rightarrow\infty}\frac{\pi(x)}{x/\operatorname{ln}(x)}=1.\!</math>

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

:<math>\lim_{x\rightarrow\infty}\pi(x) / \operatorname{li}(x)=1\!</math>

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

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

:<math>\pi(x) = \operatorname{li}(x) + \mathrm{O} \left( x \exp \left( -\frac{\sqrt{\ln(x)}}{15} \right) \right)\!</math>

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

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

:<math> \sum_{p \le x} p^{n} \sim \pi(x^{n+1}) \sim Li(x^{n+1}).</math>

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

:{| class="wikitable" style="text-align: right"
! ''x'' 
! {{pi}}(''x'')
! {{pi}}(''x'') &minus; ''x'' / ln ''x''
! li(''x'') &minus; {{pi}}(''x'')
! ''x'' / {{pi}}(''x'')
!x / ln x  % Error
|-
| 10
| 4
| &minus;0.3
| 2.2
| 2.500
| -7.5%
|-
| 10<sup>2</sup>
| 25
| 3.3
| 5.1
| 4.000
|13.20%
|-
| 10<sup>3</sup>
| 168
| 23
| 10
| 5.952
|13.69%
|-
| 10<sup>4</sup>
| 1,229
| 143
| 17
| 8.137
|11.64%
|-
| 10<sup>5</sup>
| 9,592
| 906
| 38
| 10.425
|9.45%
|-
| 10<sup>6</sup>
| 78,498
| 6,116
| 130
| 12.740
|7.79%
|-
| 10<sup>7</sup>
| 664,579
| 44,158
| 339
| 15.047
|6.64%
|-
| 10<sup>8</sup>
| 5,761,455
| 332,774
| 754
| 17.357
|5.78%
|-
| 10<sup>9</sup>
| 50,847,534
| 2,592,592
| 1,701
| 19.667
|5.10%
|-
| 10<sup>10</sup>
| 455,052,511
| 20,758,029
| 3,104
| 21.975
|4.56%
|-
| 10<sup>11</sup>
| 4,118,054,813
| 169,923,159
| 11,588
| 24.283
|4.13%
|-
| 10<sup>12</sup>
| 37,607,912,018
| 1,416,705,193
| 38,263
| 26.590
|3.77%
|-
| 10<sup>13</sup>
| 346,065,536,839
| 11,992,858,452
| 108,971
| 28.896
|3.47%
|-
| 10<sup>14</sup>
| 3,204,941,750,802
| 102,838,308,636
| 314,890
| 31.202
|3.21%
|-
| 10<sup>15</sup>
| 29,844,570,422,669
| 891,604,962,452
| 1,052,619
| 33.507
|2.99%
|-
| 10<sup>16</sup>
| 279,238,341,033,925
| 7,804,289,844,393
| 3,214,632
| 35.812
|2.79%
|-
| 10<sup>17</sup>
| 2,623,557,157,654,233
| 68,883,734,693,281
| 7,956,589
| 38.116
|2.63%
|-
| 10<sup>18</sup>
| 24,739,954,287,740,860
| 612,483,070,893,536
| 21,949,555
| 40.420
|2.48%
|-
| 10<sup>19</sup>
| 234,057,667,276,344,607
| 5,481,624,169,369,960
| 99,877,775
| 42.725
|2.34%
|-
| 10<sup>20</sup>
| 2,220,819,602,560,918,840
| 49,347,193,044,659,701
| 222,744,644
| 45.028
|2.22%
|-
| 10<sup>21</sup>
| 21,127,269,486,018,731,928
| 446,579,871,578,168,707
| 597,394,254
| 47.332
|2.11%
|-
| 10<sup>22</sup>
| 201,467,286,689,315,906,290
| 4,060,704,006,019,620,994
| 1,932,355,208
| 49.636
|2.02%
|-
| 10<sup>23</sup>
| 1,925,320,391,606,803,968,923
| 37,083,513,766,578,631,309
| 7,250,186,216
| 51.939
|1.93%
|-
| 10<sup>24</sup>
| 18,435,599,767,349,200,867,866
| 339,996,354,713,708,049,069
| 17,146,907,278
| 54.243
|1.84%
|-
| 10<sup>25</sup>
| 176,846,309,399,143,769,411,680
| 3,128,516,637,843,038,351,228
| 55,160,980,939
| 56.546
|1.77%
|-
| 10<sup>26</sup>
| 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%
|-
|10<sup>27</sup>
|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'')的方法==

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

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

:<math>\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,</math>

（其中<math>\lfloor\cdot\rfloor</math>是[[取整函数]]）。因此这个数等于：

:<math>\pi(x)-\pi\left(\sqrt{x}\right)+1\,</math>

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

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

:<math>\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right).\,</math>

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

:<math>\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).\,</math>

利用这种方法，梅塞尔计算了<math>x</math>等于5&times;10<sup>5</sup>、10<sup>6</sup>、10<sup>7</sup>以及10<sup>8</sup>时<math>\pi(x)</math>的值。

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

:<math>\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n),\,</math>

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

:<math>\pi(m)=\Phi(m,n)+n-1-P_2(m,n).</math>

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

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

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

#<math>\Phi(m,0)=\lfloor m\rfloor;\,</math>
#<math>\Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right).\,</math>

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

==其它素数计数函数==

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

:<math>\Pi_0(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)</math>

其中''p''是素数。

也可以写成以下公式：

:<math>\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})</math>

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

:<math>\pi_0(x) = \lim_{\varepsilon \rightarrow 0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2.</math>

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

:<math>\pi_{0}(x) = \sum_{n=1}^\infty \frac{\mu(n)}n \Pi_0(x^{1/n})</math>

知道了[[黎曼ζ函数]]的对数与[[馮·曼戈爾特函數]]<math>\Lambda</math>之间的关系，并利用[[佩龙公式]]，可得：

:<math>\ln \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s+1}\,dx</math>

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

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

Pierre Dusart 在2010年证明：
:<math> 
\frac {x} {\ln x - 1} < \pi(x) 
\!</math>   （其中<math>x \ge 5393</math>）

:<math> 
\pi(x) <  \frac {x} {\ln x - 1.1}
\!</math>   （其中<math>x \ge 60184</math>）

第''n''个素数''p''<sub>''n''</sub>的不等式：
:<math> 
n \ln n +  n \ln \ln n - n < p_n < n \ln n +  n \ln \ln n 
\!</math>
左面的不等式当n ≥ 2时成立，右面的不等式当n ≥ 6时成立，上限由Rosser（1941）提出，下限由Dusrat（1999）提出。

第''n''个素数的一个估计是：
:<math> 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).
</math>

==参考文献==
*{{cite book | first=Eric | last = Bach | coauthors=Shallit, Jeffrey | year=1996 | title=Algorithmic Number Theory | publisher= MIT Press| id= ISBN 0-262-02405-5 | pages=volume 1 page 234 section 8.8}}

* Marc Deléglise and Jöel Rivat, ''[http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf Computing <math>\pi(x)</math>: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method]{{Wayback|url=http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf |date=20121106183511 }}'', ''Mathematics of Computation'', vol.&nbsp;'''65''', number&nbsp;33, January 1996, pages 235–245

*{{cite book | first=Leonard Eugene | last=Dickson | year=2005 | title=History of the Theory of Numbers I: Divisibility and Primality | publisher=Dover Publications | id=ISBN 0-486-44232-2}}

*{{cite book | first=Kenneth | last=Ireland | coauthors=Rosen, Michael | year=1998 | title=A Classical Introduction to Modern Number Theory  | edition=Second edition | publisher=Springer | id=ISBN 0-387-97329-X }}

* {{MathWorld|title=Riemann Prime Counting Function|urlname=RiemannPrimeCountingFunction}}

* 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 [http://www.ieeta.pt/~tos/primes.html ''Tables of values of pi(x) and of pi2(x)''] {{Wayback|url=http://www.ieeta.pt/~tos/primes.html |date=20060824110858 }}

* Gourdon, Xavier; Sebah,Pascal [http://numbers.computation.free.fr/Constants/Primes/pixtable.html PrimePi values thru 4E22]{{Wayback|url=http://numbers.computation.free.fr/Constants/Primes/pixtable.html |date=20120617131712 }}

{{質數}}
[[Category:解析数论]]
[[Category:素数]]
[[Category:算术函数]]