看來人們在正整數領域走得越遠，素數將變得越來越稀少。人們可能想，因為它們出現的頻率越來越小，它們或許將在某處終止。早在公元前約300年時，歐幾裏得第一次證明了素數是無窮的。他用的是如下的間接論證：
設n代表最後一個素數。
現在，從所有素數直至並包含最後素數n的積得出數2×3×5×7×11×……×n。
將這個積加1,稱這數為k。k=2×3×5×7×11×…×n+1。
k是素數！假使k不是素數，那末我們用來得出上述積的素數表中一定漏掉了一個素數。我們知道2，3，5，7，11，…，n都不能整除k，因為我們每一次用2，3，5，7，11，…，n中的任何數來除時，總餘下1。因此k必然是一個新的素數。所以素數是無窮的。
作為數學中的花絮——在1至1000之間有168個素數，在1000至2000之間有135個，2000至3000間有127個，3000至4000間有120個。