质数是那些只能被自身和1整除的整数,比如前七个质数是2,3,5,7,11,13,17。图示为埃拉托色尼筛选法，可以用于寻找质数。每一个正整数都可以借助一种特定的数学结构写成质数的乘积，例如30 = 2×3×5。质数就像是构成其他整数的基本积木，而这就是人们觉得它们有趣的原因。
质数是无穷多的，而这一点早已被古希腊数学家熟知，无论你在数轴上移动多远总有一个质数在你前面。
下面是希腊最著名的数学家欧几里得的证明。假设质数是有限的。我们可以用p1, p2, p3等来表示，直到最后一个质数pn。现在定义某个数字P。比方说如果只有5个质数：p1= 2, p2= 3, p3= 5, p4= 7, p5= 11，那么存在一个数P。如果P本身是质数，那么很明显它不可能是我们列表中的一个质数，因为它比所有的质数都大。
如果P不是质数，那么，就像其他自然数一样，它一定可以写成质数的乘积。我们选一个能被P整除的质数，用p表示。可以看出，p不能是p1到pn的任何质数，否则就会出现余数1，而1不能被任何其他的自然数整除。因此，集合p1,p2,p3…pn并不能包含我们假设的所有质数。这个矛盾意味着质数一定是无限多的。
几千年来，我们一直知道有无限多个质数，但并没有一个简单的公式告诉我们它们都是多少。
强大的计算机算法使我们能够找到越来越大的质数，但却永远不可能把它们全部写下来。质数定理告诉我们质数在其他整数中的分布。它试图回答这样一个问题：“给定一个正整数n，包括n在内的所有整数，有多少个是质数?”质数定理并没有精确地回答这个问题，而是给出了一个近似值。宽泛地说，对于比较大的整数，表达式：n/ln(n)是一个很准确的质数估计，而且随着n的增大，这个估计也会变得更准确。
其中ln(n)是自然对数，可以通过计算器得到。
举个例子，让我们来看看n=1000的情况。此时所有质数可以在这个列表中查找。我们的估计是：n/ln(n) = 1000/ln(1000) ≈ 145。这是一个很准确的近似。然而，要精确地理解质数定理告诉我们的东西，我们需要说出我们所说的“一个准确的近似”是什么意思。质数定理并不是说，对于一个给定的整数n，真值和我们的近似值之间的差值接近0。
相反，它告诉我们关于“近似值占真值的百分比是多少?”的问题。回到我们n=1000的例子，真值是168，近似值是145。因此，近似构成的比例：145/168 ≈ 86%，不错。当n=100000时，包含100000的质数是9592，这是真值，估值是8686。在这种情况下，估值占真值的90%。这相比于n=1000的情况，比例从86%提升到了90%。
一般来说，质数定理告诉我们，对于n很大的情况，n/ln(n)得到的近似值几乎是真值的100%。事实上，你可以让它接近100%——只要你选择足够大的n。