素數定理
算術基本定理
素數定理（prime number theorem）是素數分佈理論的中心定理，是關於素數個數問題的一個命題： 設x≥1，以π(x)表示不超過x的素數的個數，當x→∞時，π(x)～Li(x)或π(x)～x/ln(x)。（Li(x)為對數積分）
素數定理是數論中的重要定理之一。指素數分佈的中心定理。
下面是對π(x)更好的估計：
, 其中 . 而關係式右邊第二項是誤差估計，詳見大O符號。下表比較了π(x)，和Li(x)：
（如圖所示）
素數定理可以給出第n個素數p(n)的漸近估計：它也給出從整數中抽到素數的概率。從不大於n的自然數隨機選一個，它是素數的概率大約是。這定理的式子於1798年法國數學家勒讓德提出。1896年法國數學家哈達瑪(JacquesHadamard)和比利時數學家普森(Charles Jean de la Vallée-Poussin)先後獨立給出證明。證明用到了複分析，尤其是黎曼ζ函數。因為黎曼ζ函數與π(x)關係密切，關於黎曼ζ函數的黎曼猜想對數論很重要。一旦猜想獲證，便能大大改進素數定理誤差的估計。1901年瑞典數學家Helge von Koch證明出，下式與黎曼猜想等價：
至於大O項的常數則還未知道。
在1948年, 塞爾伯格和保羅·埃爾德什首次給出素數定理的初等證明。
下面是對π(x)更好的估計： 。其中， ，是誤差估計，詳見大O符號。 下表比較了π(x)，x/ln(x)和Li(x)：
| x | π(x) | π(x) - x/ln(x) | Li(x) - π(x) | x/π(x) |
|---|---|---|---|---|
| 10 | 4 | 2 | 2.500 | |
| 10 | 25 | 3 | 5 | 4.000 |
| 10 | 168 | 23 | 10 | 5.952 |
| 10 | 1229 | 143 | 17 | 8.137 |
| 10 | 9592 | 906 | 38 | 10.430 |
| 10 | 78498 | 6116 | 130 | 12.740 |
| 10 | 664579 | 44159 | 339 | 15.050 |
| 10 | 5761455 | 332774 | 754 | 17.360 |
| 10 | 50847534 | 2592592 | 1701 | 19.670 |
| 10 | 455052511 | 20758029 | 3104 | 21.980 |
| 10 | 4118054813 | 169923159 | 11588 | 24.280 |
| 10 | 37607912018 | 1416705193 | 38263 | 26.590 |
| 10 | 346065536839 | 11992858452 | 108971 | 28.900 |
| 10 | 3204941750802 | 102838308636 | 314890 | 31.200 |
| 10 | 29844570422669 | 891604962452 | 1052619 | 33.510 |
| 10 | 279238341033925 | 7804289844392 | 3214632 | 35.810 |
| 4·10 | 1075292778753150 | 28929900579949 | 5538861 | 37.200 |
素數定理可以給出第n個素數p(n)的漸近估計：它也給出從整數中抽到素數的概率。從不大於n的自然數隨機選一個，它是素數的概率大約是。
大約在1792年，高斯（即約翰·卡爾·弗里德里希·高斯，Johann Carl Friedrich Gauß）經過深入分析和例證，對素數分佈提出猜測：。 但高斯未將自己的猜測公諸於世。1798年，法國數學家勒讓德（即阿德利昂·瑪利·埃·勒讓德，Adrien-Marie Legendre）的《論數論》（Essay on the Theory of Numbers）出版。書中，勒讓德在自己所作的某些素數計算的基礎上猜想： 。其中，常數A和常數B待定。 1808年，勒讓德把這個猜想改進為 。顯然，高斯和勒讓德提出的漸進公式是等階的，實際上都等同於猜想 （不過高斯更深刻和精確），即素數定理。
之後，俄國數學家切比雪夫（即帕夫努季·利沃維奇·切比雪夫，ПaфHутий Лbвович Чебышев）證明： 存在兩個正常數C1和C2，使不等式 對充分大的x成立，並且相當精確地定出了C1和C2的數值。他還證明，如果 的極限存在，則必定是1。
1896年，阿達馬（即雅克·所羅門·阿達馬，Jacques Solomon Hadamard，1865年－1963年）和德·拉·瓦萊布桑（Charles-Jean de la Vallée Poussin）按照波恩哈德·黎曼（B. Riemann）的思路，各自獨立地利用高深的整函數理論證明了素數定理。
1949年，塞爾伯格（即阿特勒·塞爾伯格，Atle Selberg）和埃爾德什（即保羅·埃爾德什，Paul Erdős）分別獨立地證明了素數定理。與以往證明不同的是，他們沒有用到ζ函數，而且除了極限、 和 的簡單性質外，沒有用到任何高等數學知識，甚至連微積分都沒用到。可以說，他們給出的是一個完全“初等”的證明，這一結果轟動了整個數學界。〔後來有人用 代替，用 代替 （n≤x），給出了一個連指數、對數函數都不需要的初等證明。〕塞爾伯格由於這項成就及其他工作而獲得了菲爾茲獎，埃爾德什則與陳省身一起獲得了沃爾夫數學獎。
素數定理有些初等證明只需用數論的方法。第一個初等證明由1949年由匈牙利數學家保羅·厄多斯（另譯埃爾德什、艾狄胥、“愛爾多斯”，或“愛爾多希”）和挪威數學家阿特利·西爾伯格合作得出。在此之前
一些數學家不相信能找出不需藉助艱深數學的初等證明。像英國數學家哈代便說過素數定理必須以複分析證明，顯出定理結果的「深度」。他認為只用到實數不足以解決某些問題，必須引進複數來解決。這是憑感覺說出來的，覺得一些方法比別的更高等也更厲害，而素數定理的初等證明動搖了這論調。Selberg－艾狄胥的證明正好表示，看似初等的組合數學，威力也可以很大。但是，有必要指出的是，雖然該初等證明只用到初等的辦法，其難度甚至要比用到複分析的證明遠為困難。
除2、3之外，所有6n±1都可置於一條坐標上，將6n+1分佈在左邊，那麼中心點為1，右側為6n-1。反正則中心點為-1。坐標上的每個數字產生一條波形，未被覆蓋的點就是素數。波長等於數字自身。
將每條波形拆分，坐標左邊和坐標右邊形成兩條波形，存在兩個焦點，附圖：
