素数公式Sushu gongshi

大约在公元前300年左右，欧几里得已经证明：素数的个数是无穷的(参见“素数的个数”)。既然如此，当然可以把它们按从小到大的顺序排成一个无穷数列 {P_n} (n=1, 2, 3，……):
P₁＝2, P₂＝3, P₃＝5, P₄＝7, ……
一个十分自然的想法是：我们能够求得这个数列的通项公式吗？也就是说， 是否存在这样一个公式， 设为
P_n＝f (n)
它对自然数n的每一个值，恰好给出第n个素数？退一步说，如果既不考虑素数排列的顺序，也不要求每个素数只出现一次，是否存在一个简单的一般公式，它只产生素数， 而且通过它可以得到全体素数？
寻找获得素数的一般方法——这种努力早在公元前3世纪已经有了一个极为重要的基本成果： 希腊数学家埃拉托色尼(Eratosthenes)的筛法。从那时以来，一切素数表实质上都是利用这一方法得到的。但是，随着素数的增大，相应的计算量也在迅速增大。为了求得一种更简捷的求得素数的方法，人们付出了艰巨的努力。1640年， 费尔马曾猜测：F_n＝2²ⁿ+1对一切自然数n给出素数， 但不到100年就被欧拉否决了 (参见“费尔马数”)。欧拉本人曾经研究过三项式f(x)=x2+x+41，它对于x=0, 1, …，39这40个值各给出一个素数。1933年，莱默(Lehmer, D. H.)证明：如果一个特定形式x²+x+A,A>41，也像x²+x+41那样，对所有的x=0, 1, …，A-2给出素数值，则A必须大于25·107+1。60年代后期有人证明，这样的A实际上根本不存在。已经证明：对于任何自然数n，存在一个整系数n次多项式，对于x=0, 1, 2, …， n取素数值。但是，任何多项式都不可能对每个自然数x=1, 2, 3……都给出素数值，考虑函数f (x) =x，对于一切自然数x，它显然可以产生所有的素数，不幸的是，它同样也产生所有的合数以及1。迄今为止，还不知道有什么次数大于1的多项式对无限多个自然数x给出素数值。
如果不仅仅考虑多项式，确实已发现一些函数取无限多次素数值。米尔斯(Mills, W. H.)证明：存在实数θ, 使得[θ(3n)]
对一切自然数n都给出素数值，这里[x]表示不超过x的最大整数。米尔斯证明了θ的存在，却不知道它的值。当代著名数学家哈代(Hardy)和赖特(Wright)早就指出：所谓“第n个素数Pn的一个简单的一般公式”，是指“对任何给定的n，我们用这个公式计算出Pn所花的劳动比用埃拉托色尼筛法小”。他们还说，“可以设计出许多计算P_n的‘公式’，但是其中一些只是些中看不中用的摆设， 因为它们用Pn本身来确定Pn，用它们不会得到任何未知的P_n。……其他一些可以在理论上使我们能计算出P_n，但是要以比用埃拉托色尼筛法多得多的劳动为代价。”从这一意义上说，大多数数学家都认为不存在表示素数的简单的一般公式， 然而至今却没有人对这一结论给出数学意义上的证明。