第N个素数的渐近公式

引言

根据著名的素数定理：

可以相应地推导出第N个素数的渐近公式，如下所示：

前一个公式是维基百科上的，后一个公式是《具体数学：计算机科学基础(英文版第2版)》上的，出现在第593页习题9.21答案中。这两个公式大体上相同，只有微小的差异：

• 误差估计项不同，后者的误差估计项要好于前者。
• 最后一项系数不同，前者为 5.5，后者为 5，相差 0.5。

那么，到底哪个公式好用呢？

测试程序

让我们写个 C# 程序来测试一下吧：

using System;

static class PrimeNth
{
  static long[] primes =
  {
    2, 29, 541, 7919, 104729, 1299709, 15485863, 179424673, 2038074743,
    22801763489, 252097800623, 2760727302517, 29996224275833
  };

  static void Main()
  {
    Console.WriteLine("-m ---(10^m)-th-Prime wikipedia Con.-Math");
    for (var m = 1; m < primes.Length; m++) Run(m);
  }
  
  static void Run(int m)
  {
    var n = (long)Math.Pow(10, m);
    var p = primes[m];
    var r1 = Math.Abs(Pn(n, 11) - p) / p;
    var r2 = Math.Abs(Pn(n, 10) - p) / p;
    Console.WriteLine("{0,2} {1,18:N0} {2,9:P5} {3,9:P5}", m, p, r1, r2);
  }
  
  static double Pn(long n, int k)
  {
    var lnn = Math.Log(n);
    var lnlnn = Math.Log(lnn);
    var pnn = lnn + lnlnn - 1 + (lnlnn - 2) / lnn
      - (lnlnn * lnlnn - 6 * lnlnn + k) / 2 / lnn / lnn; 
    return n * pnn;
  }
}

这个程序第5行到第9行的数组存放的是第10⁰、10¹、...、10¹²个素数，数据来源于参考资料[1]。

编译和运行

在 Windows 7 操作系统 .NET Framework 4.5 环境下编译和运行：

D:\work> csc PrimeNth.cs
Microsoft(R) Visual C# 编译器版本 4.0.30319.17929
用于 Microsoft(R) .NET Framework 4.5
版权所有 (C) Microsoft Corporation。保留所有权利。

D:\work> PrimeNth
-m ---(10^m)-th-Prime wikipedia Con.-Math
 1                 29 65.54467% 62.29274%
 2                541  8.84689%  8.41110%
 3              7,919  1.53106%  1.39874%
 4            104,729  0.32161%  0.26533%
 5          1,299,709  0.08377%  0.05475%
 6         15,485,863  0.03145%  0.01453%
 7        179,424,673  0.00010%  0.01083%
 8      2,038,074,743  0.00019%  0.00742%
 9     22,801,763,489  0.00085%  0.00595%
10    252,097,800,623  0.00058%  0.00433%
11  2,760,727,302,517  0.00046%  0.00329%
12 29,996,224,275,833  0.00031%  0.00250%

从上述结果可以看出：

• 在第10⁷到10¹²个素数之间，维基百科上的公式的相对误差比《具体数学》上的公式的相对误差要好。
• 从第10⁷个素数开始，维基百科上的公式的相对误差逐渐增大，而《具体数学》上的公式的相差误差逐渐减小。
• 从发展趋势来说，《具体数学》上的公式应该比维基百科上的公式要好。

参考资料

1. The Prime Database: The Nth Prime Page
2. Wikipedia: Prime number theorem
3. Wolfram MathWorld: Prime Formulas
4. Concrete MathEmatics: A Foundation for Computer Science, Second Edition