素数公式

-{zh-cn:质数公式;zh-tw:質數公式}-，又称-{zh-cn:素数公式;zh-tw:素數公式}-，在数学领域中，表示一种能够僅产生质数的公式。即是说，这个公式能够一个不漏地产生所有的质数，并且对每个输入的值，此公式产生的结果都是质数。由于质数的个数是可数的，因此一般假设输入的值是自然数集（或整数集及其它可数集）。迄今为止，人们尚未找到易于计算且符合上述條件的质数公式，但对于质数公式应该具备的性质已经有了大量的研究。

多项式形式的素数公式

可以证明，一个整系數多项式 ，如果不是常數函數的话，不会是一个素数公式。证明很简单：假设这样的一个多项式  存在。那么  将是一个素数 。接下来考虑  的值。由于，對于任意整數 ，我们有 ，從而  是  的倍数，但已然假设  是素数公式，所以 必须是素数，于是它就只能等于 。也就是說，对于任意的 ， 都是多项式  的一個根。但根據代數基本定理，一個非零的整系數多項式不可能有無窮多個根。故此， 只能是常数函數。

应用代数数理论，可以证明更强的结果：不存在能够对几乎所有自然数输入，都能产生素数的非常数的多项式P(n)。

欧拉在1772年发现，对于小于40的所有自然数，多项式

的值都是素数。对于前几个自然数 ，多项式的值是41, 43, 47, 53, 61, 71...。当  等于40时，多项式的值是1681=41×41，是一个合数。实际上，当  能被41整除的时候， 也能被41整除，因而是合数。这个公式和所谓的质数螺旋有关，也和黑格納數有關。若  時，其對應的多項式也有類似的性質，而  也是黑格納數。

狄利克雷定理证明了，对于互素的a和b， 線性函數  能产生无穷多个质数（尽管不是对于所有的自然数 ）。至于是否存在次数大于等于2的多项式，满足对无穷多个整数，都能取到素数值，目前还没有结论。

此外，格林-陶定理证明了另一结论：对于每个正整数 ，都存在着整数对 , ，使得对于每个0与  之间的 ， 都是素数。然而，对于比较大的 ，找出  和  是很困难的。目前最好的结果是对于 ，
P(n) = 5283234035979900n + 43142746595714191（）

丢番图方程形式的素数公式

一个很著名的素数公式是以下的有26个未知数的由14个方程组成的丢番图方程组Jones et al.（1976）：

对于这个方程组的所有正整数解：， 都是素数。可以把这个公式改写成多项式的形式：将14个等式记作 ，那么可以说，多项式 的输入值是正整数时，其值域的正值部分就是所有素数。

根据尤里·马季亚谢维奇的一个定理，如果一个集合能够被定义成一个丢番图方程的解集，那么就可以被定义为一个只有9个未知数的丢番图方程的解集。于是，素数集合可以被定义为一个只含10个变元的多项式的正值解集。然而，这个多项式的次数极大（在1045数量级），另一方面，也存在次数不超过4的多项式，未知数个数是58个。

 带高斯符號的素数公式 

利用高斯符號，可以建立一些第  个素数的表达式：

 Mills公式 

第一个带高斯函数的素数公式由W. H. Mills在1947年构造。他证明了存在实数  使得数列

中的每个数都是素数。最小的  称为米爾斯常數，如果黎曼猜想成立，它的值大約為：（）。
这个素数公式并没有什么实际价值，因为人们对  的性质所知甚少，甚至不知道  是否為有理数。而且，除了用素数值逼近外，没有其他计算  的方法。

威尔逊定理的利用

使用威尔逊定理，可以建立一些其他的素数公式。以下的公式也没有什么实际价值，大多数的素性测试都比它远为有效。

我们定义

或者

这两种定义是等价的。就是小于  的素数个数。于是，我们可以定义第  个素数如下：

另一个用高斯函数的例子

这个例子没有用到阶乘和威尔逊定理，但也大量应用了高斯函数（S. M. Ruiz 2000）。首先定义：


然后就有第  个素数的表达式：

递推关系
另外一个素数公式由以下递推关系組成的數列，其前後項的差來定义：

其中  表示  和  的最大公因數。这个数列的开始几项  是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 。证明了这个数列只含有一和素数。

其他公式
 威尔逊定理衍生公式 

其中，素数2出现无限多次，其余的素数恰好出现一次。实际上，当  是素数  的时候，由威尔逊定理，等于p-2，于是，当n+1是合数的时候，等于0，于是得到2。

參考資料

参见
素数
質數定理
哥德巴赫猜想
双生质数
埃拉托斯特尼筛法
费马数
X²+1素数

Category:素数
Category:趣味數學
Category:数学公式