菜单图标 主题
Search

素数计数函数

下载 Mathematica 笔记本下载 Wolfram 笔记本
PrimeCountingFunction

素数计数函数是函数 pi(x)，它给出小于或等于给定数 x 的素数的数量（Shanks 1993, p. 15）。例如，没有小于或等于 <=1 的素数，所以 pi(1)=0。有一个素数 (2) 小于或等于 <=2，所以 pi(2)=1。有两个素数（2 和 3）小于或等于 <=3，所以 pi(3)=2。以此类推。

素数计数函数的符号 pi(n) 有点不幸，因为它与常数 pi=3.1415... 没有任何关系。这个符号是由数论学家 Edmund Landau 在 1909 年引入的，现在已经成为标准。正如 Derbyshire (2004, p. 38) 所说，“我很抱歉；这不是我的错。你只能忍受它。”

令 p_n 表示第 n 个素数，p_n 是 pi(n) 的右逆，因为

pi(p_n)=n
(1)

对于所有正整数。此外，

p_(pi(n))=n
(2)

当且仅当 当且仅当 n 是素数。

对于 n=1, 2, ...，pi(n) 的前几个值是 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (OEIS A000720)。给出数字 x 的素数计数函数的 Wolfram 语言 命令是PrimePi[x]，它适用于最大值约为 x approx 8×10^(13)。

符号 pi_(a,b)(x) 用于表示模素数计数函数，即形式为 ak+b 且小于或等于 x 的素数的数量 (Shanks 1993, pp. 21-22)。

下表给出了 10 的幂的 pi(n) 值 (OEIS A006880)，扩展了其他印刷表格 (例如，Hardy and Wright 1979, p. 4; Shanks 1993, pp. 242-243; Ribenboim 1996, p. 237; Derbyshire 2004, p. 35)。请注意，Meissel (1885) 错误地计算了 pi(10^9) 为 50847478，误差为 56 (Havil 2003, p. 171)，这个结果被 Hardy and Wright (1979) 和 Hardy (1999) 引用，有时（错误地）被称为 Bertelsen 数。pi(10^(20)) 的值来自 Deleglise 和 Rivat (1996)，而 X. Gourdon 在 2000 年 10 月 27 日报告了 pi(10^(21))。Oliveira e Silva 和 X. Gourdon 独立计算了 pi(10^(22)) 和 pi(10^(23)) 的值，但在 Gourdon 的计算中发现了一个错误。pi(10^(23)) 的值由 Tomás Oliveira e Silva 计算，他使用硬件和程序参数的集合验证了这个结果（私人通信，2008 年 4 月 7 日）。（Oliveira e Silva 和 X. Gourdon 独立计算的 pi(x) 值对于所有高达 10^(22) 的 10 的幂都一致。）Büthe (2014) 计算了 pi(10^(25))，Staple 在 2014 年计算了 pi(10^(26)) (Staple 2015)，D. Baugh 和 K. Walisch (2015) 使用了 pi(10^(27)) 计算了primecount快速素数计数函数实现 (Walisch)。

npi(10^n)参考
14古代
225L. Pisano (1202; Beiler)
3168F. van Schooten (1657; Beiler)
41229F. van Schooten (1657; Beiler)
59592T. Brancker (1668; Beiler)
678498A. Felkel (1785; Beiler)
7664579J. P. Kulik (1867; Beiler)
85761455Meissel (1871; 已修正)
950847534Meissel (1886; 已修正)
10455052511Lehmer (1959; 已修正)
114118054813Bohmann (1972; 已修正)
1237607912018
13346065536839
143204941750802Lagarias et al. (1985)
1529844570422669Lagarias et al. (1985)
16279238341033925Lagarias et al. (1985)
172623557157654233M. Deleglise 和 J. Rivat (1994)
1824739954287740860Deleglise 和 Rivat (1996)
19234057667276344607M. Deleglise (1996 年 6 月 19 日)
202220819602560918840M. Deleglise (1996 年 6 月 19 日)
2121127269486018731928pi(x) 项目 (2000 年 12 月)
22201467286689315906290P. Demichel 和 X. Gourdon (2001 年 2 月)
231925320391606803968923T. Oliveira e Silva (私人通信，2008 年 4 月 7 日)
2418435599767349200867866Platt
25176846309399143769411680Büthe (2014)
261699246750872437141327603Staple (2015)
2716352460426841680446427399D. Baugh 和 K. Walisch (2015)

数论中最基本和最重要的结果之一是 pi(n) 在 n 变大时的渐近形式。这由素数定理给出，该定理指出

pi(n)∼Li(n),
(3)

其中 Li(x) 是对数积分，∼ 是渐近符号。这个关系最初由高斯在 1792 年（他 15 岁时）提出，尽管直到 1849 年写给 Johann Encke 的一封信中才透露，直到 1863 年才发表 (Gauss 1863; Havil 2003, pp. 176-177)。

PrimeCountingFunctions

下表比较了素数计数函数 pi(x)、黎曼素数计数函数 R(x) 和对数积分 Li(x) 对于 10 的幂，即 x=10^n。上面绘制了小 x 的相应差异。请注意，Hardy (1999, p. 26) 给出的 x=10^9 的值是不正确的。在下表中，[x] 表示最近整数函数。Borwein 和 Bailey (2003, p. 65) 给出了一个类似的表格，比较了 pi(10^n) 和 Li(10^n)。

SloaneA057794A057752
n[pi(10^n)-R(10^n)][pi(10^n)-Li(10^n)]
11-2
21-5
30-10
42-17
5-5-38
629-130
788-339
897-754
9-79-1701
10-1828-3104
11-2318-11588
12-1476-38263
13-5773-108971
14-19200-314890
1573218-1052619
16327052-3214632
17-598255-7956589
18-3501366-21949555
1923884333-99877775
20-4891825-222744644
21-86432204-597394254
22-127132665-1932355208

素数计数函数可以用勒让德公式、莱梅公式、梅普斯方法或梅塞尔公式表示。Berndt (1994) 简要介绍了计算 pi(n) 的尝试历史。下表取自 Riesel (1994)，其中 O(x) 是渐近符号。

方法时间复杂度存储复杂度
Lagarias-Miller-OdlyzkoO(x^(2/3+epsilon))O(x^(1/3+epsilon))
Lagarias-Odlyzko 1O(x^(3/5+epsilon))O(x^epsilon)
Lagarias-Odlyzko 2O(x^(1/2+epsilon))O(x^(1/4+epsilon))
勒让德公式O(x)O(x^(1/2))
莱梅O(x/(lnx)^4)O(x^(1/3)/lnx)
梅普斯方法O(x^(0.7))O(x^(0.7))
梅塞尔O(x/(lnx)^3)O(x^(1/2)/lnx)
PrimePiHarmonic

Locker-Ernst (Locker-Ernst 1959; Panaitopol 1999; Havil 2003, pp. 179-180) 提出的一个近似公式（如上图所示）由下式给出

pi(n) approx n/(h_n),
(4)

其中 h_n 与调和数 H_n 的关系为 h_n=H_n-3/2。对于 50<=n<=1000，此公式在实际值的 approx 2 范围内。pi(n)-n/h_n>0 为正值的 n 值是 1, 109, 113, 114, 199, 200, 201, ... (OEIS A051046)。Panaitopol (1999) 表明，对于所有 n>=1429，此量为正。

pi(n) 的上界由下式给出

pi(n)<(1.25506n)/(lnn)
(5)

对于 n>1，下界由下式给出

n/(lnn)<pi(n)
(6)

对于 n>=17 (Rosser 和 Schoenfeld 1962)。

Hardy 和 Wright (1979, p. 414) 给出了公式

pi(n)=-1+sum_(j=3)^n[(j-2)!-j|_((j-2)!)/j_|]
(7)

对于 n>3，其中 |_x_| 是向下取整函数。

素数计数函数的修改版本由下式给出

pi_0(p)={pi(p) for p composite; pi(p)-1/2 for p prime
(8)
pi_0(p)=sum_(n=1)^infty(mu(x)f(x^(1/n)))/n,
(9)

其中 mu(n) 是莫比乌斯函数，f(x) 是黎曼素数计数函数。

Ramanujan 还表明

(dpi(x))/(dx)∼1/(xlnx)sum_(n=1)^infty(mu(n))/nx^(1/n),
(10)

其中 mu(n) 是莫比乌斯函数 (Berndt 1994, p. 117; Havil 2003, p. 199)。

使得 x>=npi(x) 对于 n=2, 3, ... 成立的最小 x 是 2, 27, 96, 330, 1008, ... (OEIS A038625)，相应的 pi(x) 是 1, 9, 24, 66, 168, 437, ... (OEIS A038626)。x=npi(x) 对于 n=2, 3, ... 的解的数量是 4, 3, 3, 6, 7, 6, ... (OEIS A038627)。

Ramanujan 表明，对于足够大的 x，

pi^2(x)<(ex)/(lnx)pi(x/e).
(11)

这对于 x=6, 9, 10, 12, 14, 15, 16, 18, ... (OEIS A091886) 成立。已知不等式不成立的最大素数是 38358837677 (Berndt 1994, pp. 112-113)。相关的不等式

[li(x)]^2<(ex)/(lnx)li(x/e)
(12)

其中

li(x)=int_0^x(dt)/(lnt),
(13)

对于 x>=2418 和没有更小的数字成立 (Berndt 1994, p. 114)。

另请参阅

Bertelsen 数, 切比雪夫定理, 等数, 勒让德常数, 勒让德公式, Lehmer-Schur 方法, 对数积分, 梅普斯方法, 模素数计数函数, 素数算术级数, 素数计数串联常数, 素数, 素数定理, 黎曼素数计数函数 在 MathWorld 课堂中探索此主题

相关 Wolfram 站点

http://functions.wolfram.com/NumberTheoryFunctions/PrimePi/

使用 Wolfram|Alpha 探索

参考文献

Baugh, D. 和 Walisch, K. "New Confirmed pi(1027) Prime Counting Function Record." https://www.mersenneforum.org/showthread.php?t=20473. 2015 年 9 月 6 日。Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, p. 218, 1966.Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, pp. 134-135, 1994.Booker, A. "The Nth Prime Page." http://primes.utm.edu/nthprime/.Borwein, J. 和 Bailey, D. "Prime Numbers and the Zeta Function." Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 63-72, 2003.Brent, R. P. "Irregularities in the Distribution of Primes and Twin Primes." Math. Comput. 29, 43-56, 1975.Büthe, J. "A Practical Analytic Method for Calculating pi(x) II." 2014 年 10 月 26 日。 http://arxiv.org/abs/1410.7008.Caldwell, C. "How Many Primes Are There?" http://primes.utm.edu/howmany.shtml.Deleglise, M. 和 Rivat, J. "Computing pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko Method." Math. Comput. 65, 235-245, 1996.Derbyshire, J. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. New York: Penguin, 2004.Finch, S. R. "Hardy-Littlewood Constants." §2.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 84-94, 2003.Forbes, T. "Prime k-tuplets." http://anthony.d.forbes.googlepages.com/ktuplets.htm.Gauss, C. F. Werke, Band 10, Teil I. p. 10, 1863.Gourdon, X. "New Record Computation for pi(x), x=10^21." 2000 年 10 月 27 日。 http://listserv.nodak.edu/scripts/wa.exe?A2=ind0010&L=nmbrthry&P=2988.Guiasu, S. "Is There Any Regularity in the Distribution of Prime Numbers at the Beginning of the Sequence of Positive Integers?" Math. Mag. 68, 110-121, 1995.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. 和 Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 164-188, 2003.Lagarias, J.; Miller, V. S.; 和 Odlyzko, A. "Computing pi(x): The Meissel-Lehmer Method." Math. Comput. 44, 537-560, 1985.Lagarias, J. 和 Odlyzko, A. "Computing pi(x): An Analytic Method." J. Algorithms 8, 173-191, 1987.Locker-Ernst, L. "Bemerkung über die Verteilung der Primzahlen." Elemente Math. (Basel) 14, 1-5, 1959.Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17, 179-185, 1963.Meissel, E. D. F. "Über die Bestimmung der Primzahlmenge innerhalb gegebener Grenzen." Math. Ann. 2, 636-642, 1870.Meissel, E. D. F. "Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen." Math. Ann. 25, 251-257, 1885.Nagell, T. "The Function pi(x)." §16 in Introduction to Number Theory. New York: Wiley, pp. 54-57, 1951.Panaitopol, L. "Several Approximations of pi(x)." Math. Ineq. Appl. 2, 317-324, 1999.Platt, D. "Computing pi(x) Analytically." 即将发表于 Math. Comput.Ribenboim, P. The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, 1996.Riesel, H. "The Number of Primes Below x." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 10-12, 1994.Rosser, J. B. 和 Schoenfeld, L. "Approximate Formulas for Some Functions of Prime Numbers." Illinois J. Math. 6, 64-97, 1962.Séroul, R. "The Function pi(x)." §8.7 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 175-181, 2000.Shallit, J. http://www.math.uwaterloo.ca/~shallit/bib/pi.bib.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993.Sloane, N. J. A. Sequences A000720/M0256, A006880/M3608, A038625, A038626, A038627, A052434, A052435, A057752, A057794, and A091886 in "The On-Line Encyclopedia of Integer Sequences."Staple, D. B. "The Combinatorial Algorithm for Computing pi(x)." https://arxiv.org/abs/1503.01839. 2015 年 5 月 28 日。Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 74-76, 1991.Walisch, K. "Fast Prime Counting Function Implementations." https://github.com/kimwalisch/primecount.Wolf, M. "Unexpected Regularities in the Distribution of Prime Numbers." http://www.ift.uni.wroc.pl/~mwolf/.

在 Wolfram|Alpha 中被引用

素数计数函数

引用为

Weisstein, Eric W. "Prime Counting Function." 来自 MathWorld--Wolfram 网络资源. https://mathworld.net.cn/PrimeCountingFunction.html

主题分类