fbpx
维基百科

素数计数函数

数学中,素数计数函数是一个用来表示小于或等于某个实数x素数的个数的函数,记为

π(n)的最初60个值

历史

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

 

也就是

 

这就是素数定理。一个等价的表述,是:

 

其中 对数积分函数。这个定理在1896年得到证明。证明用到了黎曼ζ函数的性质。

目前已知 还有更精确的估计,例如:

 

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

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

 

π(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)的方法

如果 不太大,一个简单的计算 的方法就是使用埃拉托斯特尼筛法

一个比较复杂的计算 的方法是勒让德发现的:给定 ,如果 、  、 ……、  是不同的素数,则小于 且不能被任何一个 整除的整数个数是:

 

(其中 取整函数)。因此这个数等于:

 

其中 是小于或等于 的平方根的素数的个数。

恩斯特·梅塞尔在1870年和1885年发表的一系列文章中,描述并使用了一个计算 的组合方法。设  , …,  是最初 个素数,不大于 且不能整除任何一个 的自然数个数记为 ,那么:

 

给定一个自然数 ,如果  ,那么:

 

利用这种方法,梅塞尔计算了 等于5×105、106、107以及108 的值。

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

 

这个和实际上只有有限个非零的项。设 为一个整数,使得 ,并设 。那么当  ≥ 3时,  。因此:

 

 的计算可以用这种方法来获得:

 

另一方面, 的计算可以用以下规则来完成:

  1.  
  2.  

利用这种方法,勒梅尔计算了 

其它素数计数函数

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

 

其中p是素数。

也可以写成以下公式:

 

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

 

利用默比乌斯反演公式,可得:

 

知道了黎曼ζ函数的对数与馮·曼戈爾特函數 之间的关系,并利用佩龙公式,可得:

 

不等式

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

 ,左不等式适用于x ≥ 17,右不等式适用于x>1,常数1.25506为  保留5位有效小数, 最大值为x = 113。

Pierre Dusart 在2010年证明:

  (其中 
  (其中 

n个素数pn的不等式:

 

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

n个素数的一个估计是:

 

参考文献

  • Bach, Eric; Shallit, Jeffrey. Algorithmic Number Theory. MIT Press. 1996: volume 1 page 234 section 8.8. ISBN 0-262-02405-5. 
  • Marc Deléglise and Jöel Rivat, Computing  : 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. 
  • 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(页面存档备份,存于互联网档案馆

素数计数函数, 在数学中, 是一个用来表示小于或等于某个实数x的素数的个数的函数, 记为π, displaystyle, 的最初60个值, 目录, 历史, x和li, 计算π, 的方法, 其它, 不等式, 参考文献历史, 编辑在数论中, 的增长率引起了很大的兴趣, 在18世纪末, 高斯和勒让德曾猜想这个函数大约为, displaystyle, operatorname, 也就是, displaystyle, rightarrow, infty, frac, operatorname, 这就是素数定理, 一个等价的表. 在数学中 素数计数函数是一个用来表示小于或等于某个实数x的素数的个数的函数 记为p x displaystyle pi x p n 的最初60个值 目录 1 历史 2 p x x ln x和li x 3 计算p x 的方法 4 其它素数计数函数 5 不等式 6 参考文献历史 编辑在数论中 素数计数函数的增长率引起了很大的兴趣 在18世纪末 高斯和勒让德曾猜想这个函数大约为 x ln x displaystyle x operatorname ln x 也就是 lim x p x x ln x 1 displaystyle lim x rightarrow infty frac pi x x operatorname ln x 1 这就是素数定理 一个等价的表述 是 lim x p x li x 1 displaystyle lim x rightarrow infty pi x operatorname li x 1 其中li x displaystyle operatorname li x 是对数积分函数 这个定理在1896年得到证明 证明用到了黎曼z函数的性质 目前已知p x displaystyle pi x 还有更精确的估计 例如 p x li x O x exp ln x 15 displaystyle pi x operatorname li x mathrm O left x exp left frac sqrt ln x 15 right right 其中O是大O符号 1948年 阿特勒 塞爾伯格和保罗 埃尔德什不使用函数或复分析证明了素数定理 另外一个关于素数计数函数的增长率的猜想 是 p x p n p x n 1 L i x n 1 displaystyle sum p leq x p n sim pi x n 1 sim Li x n 1 p x x ln x和li x 编辑x p x p x x ln x li x p x x p x x ln x Error10 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 计算p x 的方法 编辑如果x displaystyle x 不太大 一个简单的计算p x displaystyle pi x 的方法就是使用埃拉托斯特尼筛法 一个比较复杂的计算p x displaystyle pi x 的方法是勒让德发现的 给定x displaystyle x 如果p 1 displaystyle p 1 p 2 displaystyle p 2 p k displaystyle p k 是不同的素数 则小于x displaystyle x 且不能被任何一个p i displaystyle p i 整除的整数个数是 x i x p i i lt j x p i p j i lt j lt k x p i p j p k displaystyle lfloor x rfloor sum i left lfloor frac x p i right rfloor sum i lt j left lfloor frac x p i p j right rfloor sum i lt j lt k left lfloor frac x p i p j p k right rfloor cdots 其中 displaystyle lfloor cdot rfloor 是取整函数 因此这个数等于 p x p x 1 displaystyle pi x pi left sqrt x right 1 其中p 1 p 2 p k displaystyle p 1 p 2 dots p k 是小于或等于x displaystyle x 的平方根的素数的个数 恩斯特 梅塞尔在1870年和1885年发表的一系列文章中 描述并使用了一个计算p x displaystyle pi x 的组合方法 设p 1 displaystyle p 1 p 2 displaystyle p 2 p n displaystyle p n 是最初n displaystyle n 个素数 不大于m displaystyle m 且不能整除任何一个p i displaystyle p i 的自然数个数记为F m n displaystyle Phi m n 那么 F m n F m n 1 F m p n n 1 displaystyle Phi m n Phi m n 1 Phi left left frac m p n right n 1 right 给定一个自然数m displaystyle m 如果n p m 3 displaystyle n pi left sqrt 3 m right 且m p m n displaystyle mu pi left sqrt m right n 那么 p m F m n n m 1 m 2 m 2 1 k 1 m p m p n k 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 利用这种方法 梅塞尔计算了x displaystyle x 等于5 105 106 107以及108时p x displaystyle pi x 的值 1959年 德里克 亨利 勒梅尔推广并简化了梅塞尔的方法 对于实数m displaystyle m 和自然数n displaystyle n 和k displaystyle k 定义P k m n displaystyle P k m n 为不大于m且正好有k个大于p n displaystyle p n 的素因子的整数个数 更进一步 设定P 0 m n 1 displaystyle P 0 m n 1 那么 F m n k 0 P k m n displaystyle Phi m n sum k 0 infty P k m n 这个和实际上只有有限个非零的项 设y displaystyle y 为一个整数 使得m 3 y m displaystyle sqrt 3 m leq y leq sqrt m 并设n p y displaystyle n pi y 那么当k displaystyle k 3时 P 1 m n p m n displaystyle P 1 m n pi m n 且P k m n 0 displaystyle P k m n 0 因此 p m F m n n 1 P 2 m n displaystyle pi m Phi m n n 1 P 2 m n P 2 m n displaystyle P 2 m n 的计算可以用这种方法来获得 P 2 m n y lt p m p m p p p 1 displaystyle P 2 m n sum y lt p leq sqrt m left pi left frac m p right pi p 1 right 另一方面 F m n displaystyle Phi m n 的计算可以用以下规则来完成 F m 0 m displaystyle Phi m 0 lfloor m rfloor F m b F m b 1 F m p b b 1 displaystyle Phi m b Phi m b 1 Phi left frac m p b b 1 right 利用这种方法 勒梅尔计算了p 10 10 displaystyle pi left 10 10 right 其它素数计数函数 编辑我们也使用其它的素数计数函数 因为它们更方便 其中一个是黎曼的素数计数函数 通常记为P 0 x displaystyle Pi 0 x 这个函数在自变量为素数的幂pn时突然增加了1 n 而该点的值则是两边的平均值 我们可以用以下公式来定义P 0 x displaystyle Pi 0 x P 0 x 1 2 p n lt x 1 n p n x 1 n displaystyle Pi 0 x frac 1 2 bigg sum p n lt x frac 1 n sum p n leq x frac 1 n bigg 其中p是素数 也可以写成以下公式 P 0 x 2 x L n ln n 1 2 L x ln x n 1 1 n p 0 x 1 n 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 其中L n 是馮 曼戈爾特函數 p 0 x lim e 0 p x e p x e 2 displaystyle pi 0 x lim varepsilon rightarrow 0 frac pi x varepsilon pi x varepsilon 2 利用默比乌斯反演公式 可得 p 0 x n 1 m n n P 0 x 1 n displaystyle pi 0 x sum n 1 infty frac mu n n Pi 0 x 1 n 知道了黎曼z函数的对数与馮 曼戈爾特函數L displaystyle Lambda 之间的关系 并利用佩龙公式 可得 ln z s s 0 P 0 x x s 1 d x displaystyle ln zeta s s int 0 infty Pi 0 x x s 1 dx 不等式 编辑下面是一些有用的p x 不等式 x ln x lt p x lt 1 25506 x ln x displaystyle frac x ln x lt pi x lt 1 25506 frac x ln x 左不等式适用于x 17 右不等式适用于x gt 1 常数1 25506为 30 ln 113 113 displaystyle frac 30 ln 113 113 保留5位有效小数 p x ln x x displaystyle frac pi x ln x x 最大值为x 113 Pierre Dusart 在2010年证明 x ln x 1 lt p x displaystyle frac x ln x 1 lt pi x 其中x 5393 displaystyle x geq 5393 p x lt x ln x 1 1 displaystyle pi x lt frac x ln x 1 1 其中x 60184 displaystyle x geq 60184 第n个素数pn的不等式 n ln n n ln ln n n lt p n lt n ln n n ln ln n displaystyle n ln n n ln ln n n lt p n lt 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 n ln ln n 2 n ln n O n ln ln n 2 ln n 2 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 Deleglise and Joel Rivat Computing p x displaystyle pi x The Meissel Lehmer Lagarias Miller Odlyzko method 页面存档备份 存于互联网档案馆 Mathematics of Computation vol 65 number 33 January 1996 pages 235 245Dickson 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 Demarches de la Geometrie et des Nombres de l Universite du BordeauxTitchmarsh E C The Theory of Functions 2nd ed Oxford England Oxford University Press 1960 Oliveira e Silva Tomas Tables of values of pi x and of pi2 x 页面存档备份 存于互联网档案馆 Gourdon Xavier Sebah Pascal PrimePi values thru 4E22 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 素数计数函数 amp oldid 74916674, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。