最小的質數

2是最小的質數，也是唯一的一個既是偶數又是質數的數．也就是説，除了2以外，質數都是奇數。

小於100的質數有如下25個：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97

質數（Prime number，又稱素數），指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數（也可定義為只有1與該數本身兩個正因數的數）。

大於1的自然數若不是素數，則稱之為合數（也稱為合成數）。例如，5是個素數，因為其正約數只有1與5。而6則是個合數，因為除了1與6外，2與3也是其正約數。算術基本定理確立了素數於數論裏的核心地位：任何大於1的整數均可被表示成一串唯一素數之乘積。為了確保該定理的唯一性，1被定義為不是素數，因為在因式分解中可以有任意多個1（如3、1×3、1×1×3等都是3的有效約數分解）。

歷史

在古埃及人的倖存紀錄中，有跡象顯示他們對素數已有部分認識：例如，在萊因德數學紙草書中的古埃及分數展開時，對素數與對合數有着完全不同的類型。不過，對素數有過具體研究的最早倖存紀錄來自古希臘。公元前300年左右的《幾何原本》包含與素數有關的重要定理，如有無限多個素數，以及算術基本定理。歐幾里得亦展示如何從梅森素數建構出完全數。埃拉託斯特尼提出的埃拉託斯特尼篩法是用來計算素數的一個簡單方法，雖然今天使用電腦發現的大素數無法使用這個方法找出。

希臘之後，到17世紀之前，素數的研究少有進展。1640年，皮埃爾·德·費馬敍述了費馬小定理（之後才被萊布尼茨與歐拉證明）。費馬亦推測，所有具22n+1形式的數均為素數（稱之為費馬數），並驗證至n=4（即216+1）不過，後來由歐拉發現，下一個費馬數232+1即為合數，且實際上其他已知的費馬數都不是素數。法國修道士馬蘭·梅森發現有的素數具2p−1的形式，其中p為素數。為紀念他的貢獻，此類素數後來被稱為梅森素數。

歐拉在數論中的成果，許多與素數有關。他證明無窮級數1/2+1/3+1/5+1/7+1/11+…會發散。1747年，歐拉證明每個完全數都確實為2p−1(2p−1)的形式，其中第二個約數為梅森素數。

19世紀初，勒讓德與高斯獨立推測，當x趨向無限大時，小於x的素數數量會趨近於x/ln(x)，其中ln(x)為x的自然對數。黎曼於1859年有關ζ函數的論文中勾勒出一個程式，導出了素數定理的證明。其大綱由雅克·阿達馬與查爾斯·貞·德·拉·瓦萊-普森所完成，他們於1896年獨立證明出素數定理。

證明一個大數是否為素數通常無法由試除法來達成。許多數學家已研究過大數的素數測試，通常侷限於特定的數字形式。其中包括費馬數的貝潘測試（1877年）、普羅絲定理（約1878年）、盧卡斯-萊默素數判定法（1856年起）及廣義盧卡斯素數測試。較近期的算法，如APRT-CL、ECPP及AKS等，均可作用於任意數字上，但仍慢上許多。

長期以來，素數被認為在純數學以外的地方只有極少數的應用。到了1970年代，發明公共密鑰加密這個概念之後，情況改變了，素數變成了RSA加密算法等一階算法之基礎。

自1951年以來，所有已知最大的素數都由電腦所發現。對更大素數的搜尋已在數學界以外的地方產生出興趣。互聯網梅森素數大搜索及其他用來尋找大素數的分散式運算計劃變得流行，在數學家仍持續與素數理論奮鬥的同時。