素数是一个极其自然的数列，以至于我们会无法抗拒地去搜寻它们的规律。然而，不存在有关素数的真正有用的公式。也就是说，没有已知的规则能够生成所有的素数，甚至无法计算出一个完全由不同的素数组成的数列。存在一些形式简洁的公式，但几乎没有实用价值，要计算其中一些的值甚至需要素数相关的知识，因此本质上它们算是作弊。形如n2＋n＋41的表达式称作多项式（polynomial），这一个多项式能够产生极其大量的素数。例如，让n依次取值1，7和20，会分别得出素数43，107和461。确实，输入n=0到n=39，这一表达式的输出都是素数。但当取n=41时，这个多项式就令我们大失所望了，因为结果会有因数41。并且，对于n=40也失败了，因为
402＋40＋41=40 (40＋1)＋41
=40×41＋41=(40＋1)41=412。
可以轻而易举地证明，一般而言没有某个多项式能给出一个素数的公式，即便允许表达式中存在高于2的幂次也不行。
的确有可能设计出仅用一两句话描述的素性检验的方法。但是，想要它们有用，还需要再快捷一点，至少在某些情况下得快于第1章中描述的直接验证方法。一个有名的结论叫作威尔逊定理（Wilson's theorem）。它的表述使用到了一类叫作阶乘（factorials）的数，我们将在第5章里再次与它相见。数n!读作“n的阶乘”，就是所有不大于n的正整数的乘积。比如，5!=5×4×3×2×1=120。威尔逊定理便是一条极其简洁的陈述：当且仅当p是1＋(p-1)!的一个因数时，数p为素数。