推荐订阅源

引言

根据著名的素数定理：

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

前一个公式是维基百科上的，后一个公式是《具体数学：计算机科学基础(英文版第2版)》上的，出现在第593页习题9.21答案中。这两个公式本质上是一样的。

测试程序

让我们写个 C# 程序来计算这个渐近公式的相对误差吧：

 1 using System;
 2 
 3 static class PrimeNth
 4 {
 5   static decimal[] primes =
 6   {
 7     2, 29, 541, 7919, 104729, 1299709, 15485863, 179424673, 2038074743,
 8     22801763489, 252097800623, 2760727302517, 29996224275833,
 9     323780508946331, 3475385758524527, 37124508045065437,
10     394906913903735329, 4185296581467695669m, 44211790234832169331m,
11     465675465116607065549m, 4892055594575155744537m
12   };
13  
14   static void Main()
15   {
16     Console.WriteLine("-m --------------(10^m)-th-prime -rel-error");
17     for (var m = 1; m < primes.Length; m++) Run(m);
18   }
19    
20   static void Run(int m)
21   {
22     var p = primes[m];
23     var r = Math.Abs(Pn((decimal)Math.Pow(10, m)) - p) / p;
24     Console.WriteLine("{0,2} {1,29:N0} {2,10:P6}", m, p, r);
25   }
26    
27   static decimal Pn(decimal n)
28   {
29     var lnn = Math.Log((double)n);
30     var lnlnn = Math.Log(lnn);
31     var pnn = lnn + lnlnn - 1 + (lnlnn - 2) / lnn
32       - (lnlnn * lnlnn - 6 * lnlnn + 11) / 2 / lnn / lnn; 
33     return n * (decimal)pnn;
34   }
35 }

这个程序第5行到第12行的数组存放的是第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 -rel-error
 1                            29 65.544667%
 2                           541  8.846891%
 3                         7,919  1.531065%
 4                       104,729  0.321614%
 5                     1,299,709  0.083770%
 6                    15,485,863  0.031450%
 7                   179,424,673  0.000099%
 8                 2,038,074,743  0.000190%
 9                22,801,763,489  0.000846%
10               252,097,800,623  0.000585%
11             2,760,727,302,517  0.000464%
12            29,996,224,275,833  0.000312%
13           323,780,508,946,331  0.000211%
14         3,475,385,758,524,527  0.000145%
15        37,124,508,045,065,437  0.000101%
16       394,906,913,903,735,329  0.000071%
17     4,185,296,581,467,695,669  0.000051%
18    44,211,790,234,832,169,331  0.000037%
19   465,675,465,116,607,065,549  0.000027%
20 4,892,055,594,575,155,744,537  0.000020%

参考资料

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