素數定理

下面是對π(x)更好的估計：

。

其中，

，

是誤差估計，詳見大O符號。

下表比較了π(x)，x/ln(x)和Li(x)：

素數定理可以給出第n個素數p(n)的漸近估計：

。它也給出從整數中抽到素數的概率。從不大於n的自然數隨機選一個，它是素數的概率大約是

。

大約在1792年，高斯（即約翰·卡爾·弗里德里希·高斯，Johann Carl Friedrich Gauß）經過深入分析和例證，對素數分佈提出猜測：

。 ^[5]  但高斯未將自己的猜測公諸於世。1798年，法國數學家勒讓德（即阿德利昂·瑪利·埃·勒讓德，Adrien-Marie Legendre）的《論數論》（Essay on the Theory of Numbers）出版。書中，勒讓德在自己所作的某些素數計算的基礎上猜想：

。其中，常數A和常數B待定。 ^[6]  1808年，勒讓德把這個猜想改進為

。顯然，高斯和勒讓德提出的漸進公式是等階的，實際上都等同於猜想

（不過高斯更深刻和精確），即素數定理。

之後，俄國數學家切比雪夫（即帕夫努季·利沃維奇·切比雪夫，ПaфHутий Лbвович Чебышев）證明： 存在兩個正常數C₁和C₂，使不等式

對充分大的x成立，並且相當精確地定出了C₁和C₂的數值。他還證明，如果

的極限存在，則必定是1。

1896年，阿達馬（即雅克·所羅門·阿達馬，Jacques Solomon Hadamard，1865年－1963年）和德·拉·瓦萊布桑（Charles-Jean de la Vallée Poussin）按照波恩哈德·黎曼（B. Riemann）的思路，各自獨立地利用高深的整函數理論證明了素數定理。

1949年，塞爾伯格（即阿特勒·塞爾伯格，Atle Selberg）和埃爾德什（即保羅·埃爾德什，Paul Erdős）分別獨立地證明了素數定理。與以往證明不同的是，他們沒有用到ζ函數，而且除了極限、

和

的簡單性質外，沒有用到任何高等數學知識，甚至連微積分都沒用到。可以説，他們給出的是一個完全“初等”的證明，這一結果轟動了整個數學界。〔後來有人用

代替

，用

代替

（n≤x），給出了一個連指數、對數函數都不需要的初等證明。〕塞爾伯格由於這項成就及其他工作而獲得了菲爾茲獎，埃爾德什則與陳省身一起獲得了沃爾夫數學獎。 ^[7-8] 

素數定理有些初等證明只需用數論的方法。第一個初等證明由1949年由匈牙利數學家保羅·厄多斯（另譯埃爾德什、艾狄胥、“愛爾多斯”，或“愛爾多希”）和挪威數學家阿特利·西爾伯格合作得出。 在此之前一些數學家不相信能找出不需藉助艱深數學的初等證明。像英國數學家哈代便説過素數定理必須以複分析證明，顯出定理結果的“深度”。他認為只用到實數不足以解決某些問題，必須引進複數來解決。這是憑感覺説出來的，覺得一些方法比別的更高等也更厲害，而素數定理的初等證明動搖了這論調。Selberg－艾狄胥的證明正好表示，看似初等的組合數學，威力也可以很大。 但是，有必要指出的是，雖然該初等證明只用到初等的辦法，其難度甚至要比用到複分析的證明遠為困難。