第N个素数的渐近公式

现在的位置: 首页 > 综合 > 正文

RSS

第N个素数的渐近公式

2012年10月31日 ⁄ 综合 ⁄ 共 1928字 ⁄ 字号小中大 ⁄ 评论关闭

引言

根据著名的素数定理：

$Pi(x)$

$Li(x)$

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

$Pn1$

$P_n=n(\ln n+\ln\ln n-1+\frac{\ln\ln n-2}{\ln n}-\frac{(\ln\ln n)^2/2-3\ln\ln n+ 5.5}{(\ln n)^2}+ O(\frac{\log\log n}{\log n})^3)$

前一个公式是维基百科上的，后一个公式是《具体数学：计算机科学基础(英文版第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%