質數（prime number）占自然數的百分比
素數是無窮多的，對這個論斷，現在所已知的最古老的檢驗方法是歐幾裏德在他的幾何原本中提出來的。他的檢驗方法可以簡單地總結如下：
取有限個數的素數，因為要做自變量我們假設全部的素數都存在，將這些素數相乘然後加1，得到的數是不會被這些素數中的任何壹個整除的，因為無論除哪個總會余1。因此這個數要麽本身就是個素數，要麽存在不在這個有限集合內的約數。因此我們開始用的集合不包含所有的素數。
別的數學家也給出了他們自己的證明。歐拉證明了全部素數的倒數和發散到無窮的。恩斯特·庫默的證明尤其簡潔，Furstenberg用壹般拓撲證明。
盡管整個素數是無窮的，仍然有人會問“100000以下有多少個素數?”，“壹個隨機的100位數多大可能是素數?”。素數定理可以回答此問題。
[編輯] 尋找素數
尋找在給定限度內的素數排列，埃拉托斯特尼篩法法是個很好的方法。然而在實際中，我們往往是想知道壹個給定數是否是素數，而不是生成壹個素數排列。進而，知道答案是很高的概率就是已經很滿意的了，用素性測試迅速地檢查壹個給定數（例如，有幾千位數的長度）是否是素數是可能的。典型的方法是隨機選取壹個數，然後圍繞著這個數和可能的素數N檢查壹些方程式。重復這個過程幾次後，它宣布這個數是明顯的合數或者可能是素數。這種方法是不完美的：對某些測試而言，例如費馬測試，不論選取了多少隨機數都有可能將壹些合數判斷成可能的素數，這就引出了另壹種數偽素數。而像米勒-拉賓測試，雖然只要選取夠多數字來檢驗方程式，就可以保證其檢驗出的質數性是正確的，但這個保證門檻的數量太過龐大，甚至比試除法所需的還要多，在有限時間內運行起來只能知道答案正確的機率很高，不能保證壹定正確。
目前最大的已知素數是232582657 ? 1（此數字位長度是9,808,358），它是在2006年9月4日由GIMPS發現。這組織也在2005年12月15日發現了目前所知第二大的已知素數230402457 ? 1（此數字位長度是9,152,052）。
數學家壹直努力找尋產生素數的公式，但截至目前為止，並沒有壹個基本函數或是多項式可以正確產生所有的素數。歷史上有許多試驗的例子：17世紀初法國數學家梅森(Mersenne)在他的壹個著作當中討論了這樣壹種我們現在稱之為梅森素數的素數，Mp=2p - 1，本來以為只要p是壹個素數，n = 2p - 1就會是壹個素數，這在p = 3，p = 5，p = 7都是正確的，但是p = 11時 }-就不是素數了。