看来人们在正整数领域走得越远，素数将变得越来越稀少。人们可能想，因为它们出现的频率越来越小，它们或许将在某处终止。早在公元前约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个。