質數計算函數

在數學中，**質數計數函數**是一個用來表示小於或等於某個實數 _x_ 的質數的個數的函數，記為 $\pi (x)$ 。

## 歷史

在數論中，質數計數函數的增長率引起了很大的興趣。在 18 世紀末，高斯和勒壤得曾猜想這個函數大約為：

　
: $x/\operatorname {ln} (x)\!$

也就是

　
: $\lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\operatorname {ln} (x)}}=1.\!$

這就是質數定理。一個等價的表述，是：

　
: $\lim _{x\rightarrow \infty }\pi (x)/\operatorname {li} (x)=1\!$

其中 $\operatorname {li} (x)$ 是對數積分函數。這個定理在 1896 年得到證明。證明用到了黎曼 ζ 函數的性質。

目前已知 $\pi (x)\!$ 還有更精確的估計，例如：

　
: $\pi (x)=\operatorname {li} (x)+\mathrm {O} \left(x\exp \left(-{\frac {\sqrt {\ln(x)}}{15}}\right)\right)\!$

其中 _O_ 是大 O 符號。1948 年，阿特勒・塞爾伯格和保羅・艾狄胥不使用函數或複分析證明了質數定理。

另外一個關於質數計數函數的增長率的猜想，是：

　
: $\sum _{p\leq x}p^{n}\sim \pi (x^{n+1})\sim Li(x^{n+1}).$

## π(_x_)、_x_ / ln _x_ 和 li (_x_)

　
:

## 計算 π(_x_) 的方法

如果 $x$ 不太大，一個簡單的計算 $\pi (x)$ 的方法就是使用埃拉托斯特尼篩法。

一個比較複雜的計算 $\pi (x)$ 的方法是勒壤得發現的：給定 $x$ ，如果 $p_{1}$ 、  $p_{2}$ 、 ……、  $p_{k}$ 是不同的質數，則小於 $x$ 且不能被任何一個 $p_{i}$ 整除的整數個數是：

　
: $\lfloor x\rfloor -\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor +\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor -\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor +\cdots ,$

（其中 $\lfloor \cdot \rfloor $ 是取整函數）。因此這個數等於：

　
: $\pi (x)-\pi \left({\sqrt {x}}\right)+1\,$

其中 $p_{1},p_{2},\dots ,p_{k}$ 是小於或等於 $x$ 的平方根的質數的個數。

恩斯特・梅塞爾在 1870 年和 1885 年發表的一系列文章中，描述並使用了一個計算 $\pi (x)$ 的組合方法。設 $p_{1}$ ,  $p_{2}$ , …,  $p_{n}$ 是最初 $n$ 個質數，不大於 $m$ 且不能整除任何一個 $p_{i}$ 的自然數個數記為 $\Phi (m,n)$ ，那麼：

　
: $\Phi (m,n)=\Phi (m,n-1)-\Phi \left(\left[{\frac {m}{p_{n}}}\right],n-1\right).\,$

給定一個自然數 $m$ ，如果 $n=\pi \left({\sqrt[{3}]{m}}\right)$ 且 $\mu =\pi \left({\sqrt {m}}\right)-n$ ，那麼：

　
: $\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$ 等於 5×105、106、107 以及 108 時 $\pi (x)$ 的值。

1959 年，德里克・亨利・勒梅爾推廣並簡化了梅塞爾的方法。對於實數 $m$ 和自然數 $n$ 和 $k$ ，定義 $P_{k}(m,n)$ 為不大於 _m_ 且正好有 _k_ 個大於 $p_{n}$ 的質因子的整數個數。更進一步，設定 $P_{0}(m,n)=1$ 。那麼：

　
: $\Phi (m,n)=\sum _{k=0}^{+\infty }P_{k}(m,n),\,$

這個和實際上只有有限個非零的項。設 $y$ 為一個整數，使得 ${\sqrt[{3}]{m}}\leq y\leq {\sqrt {m}}$ ，並設 $n=\pi (y)$ 。那麼當 $k$ ≥ 3 時， $P_{1}(m,n)=\pi (m)-n$ 且 $P_{k}(m,n)=0$ 。因此：

　
: $\pi (m)=\Phi (m,n)+n-1-P_{2}(m,n).$

 $P_{2}(m,n)$ 的計算可以用這種方法來獲得：

　
: $P_{2}(m,n)=\sum _{y<p\leq {\sqrt {m}}}\left(\pi \left({\frac {m}{p}}\right)-\pi (p)+1\right).\,$

另一方面， $\Phi (m,n)$ 的計算可以用以下規則來完成：

 1. $\Phi (m,0)=\lfloor m\rfloor ;\,$
2. $\Phi (m,b)=\Phi (m,b-1)-\Phi \left({\frac {m}{p_{b}}},b-1\right).\,$

利用這種方法，勒梅爾計算了 $\pi \left(10^{10}\right)$ 。

## 其它質數計數函數

我們也使用其它的質數計數函數，因為它們更方便。其中一個是黎曼的質數計數函數，通常記為 $\Pi _{0}(x)$ 。這個函數在自變數為質數的冪 _p_n 時突然增加了 _1/n_，而該點的值則是兩邊的平均值。我們可以用以下公式來定義 $\Pi _{0}(x)$ ：

　
: $\Pi _{0}(x)={\frac {1}{2}}{\bigg (}\sum _{p^{n}<x}{\frac {1}{n}}\ +\sum _{p^{n}\leq x}{\frac {1}{n}}{\bigg )}$

其中 _p_ 是質數。

也可以寫成以下公式：

　
: $\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})$

其中 Λ(_n_) 是馮・曼戈爾特函數，

　
: $\pi _{0}(x)=\lim _{\varepsilon \rightarrow 0}{\frac {\pi (x-\varepsilon )+\pi (x+\varepsilon )}{2}}.$

利用默比烏斯反演公式，可得：

　
: $\pi _{0}(x)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n}}\Pi _{0}(x^{1/n})$

知道了黎曼 ζ 函數的對數與馮・曼戈爾特函數 $\Lambda $ 之間的關係，並利用佩龍公式，可得：

　
: $\ln \zeta (s)=s\int _{0}^{\infty }\Pi _{0}(x)x^{-s+1}\,dx$

## 不等式

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

　
: ${\frac {x}{\ln x}}<\pi (x)<1.25506{\frac {x}{\ln x}}\!$ ，左不等式適用於 x ≥ 17，右不等式適用於 x>1，常數 1.25506 為 ${\frac {30\ln 113}{113}}$ 保留 5 位有效小數， ${\frac {\pi (x)\ln x}{x}}$ 最大值為 x = 113。

Pierre Dusart 在 2010 年證明：

　
: ${\frac {x}{\ln x-1}}<\pi (x)\!$ （其中 $x\geq 5393$ ）

　
: $\pi (x)<{\frac {x}{\ln x-1.1}}\!$ （其中 $x\geq 60184$ ）

第 _n_ 個質數 _p_n 的不等式：

　
: $n\ln n+n\ln \ln n-n<p_{n}<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+{\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.
* Marc Deléglise and Jöel Rivat, _Computing $\pi (x)$ : 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.  引文格式 1 維護：冗餘文本 (link)
* 埃里克・韋斯坦因. Riemann Prime Counting Function. MathWorld.
* 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（頁面存檔備份，存於網際網路檔案館）