素数是一个极其自然的数列,以至于我们会无法抗拒地去搜寻它们的规律。然而,不存在有关素数的真正有用的公式。也就是说,没有已知的规则能够生成所有的素数,甚至无法计算出一个完全由不同的素数组成的数列。存在一些形式简洁的公式,但几乎没有实用价值,要计算其中一些的值甚至需要素数相关的知识,因此本质上它们算是作弊。形如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为素数。