素数公式

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

多项式形式的素数公式

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

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

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

f(n)=n^{2}+n+41

的值都是素数。对于前几个自然数n = 0, 1, 2, 3...，多项式的值是41, 43, 47, 53, 61, 71...。当n等于40时，多项式的值是1681=41×41，是一个合数。实际上，当n能被41整除的时候，P(n)也能被41整除，因而是合数。这个公式和所谓的质数螺旋有关，也和黑格納數 $163=4\cdot 41-1$ 有關。若 $p=2,3,5,11,17$ 時，其對應的多項式也有類似的性質，而 $4\cdot p-1$ 也是黑格納數。

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

此外，格林-陶定理证明了另一结论：对于每个正整数k，都存在着整数对a, b，使得对于每个0与k−1之间的n， $L(n)=an+b$ 都是素数。然而，对于比较大的k，找出a和b是很困难的。目前最好的结果是对于k = 26^[1]，

P(n) = 5283234035979900n + 43142746595714191（

A204189 ）

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

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

0=wz+h+j-q

0=(gk+2g+k+1)(h+j)+h-z

0=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}

0=2n+p+q+z-e

0=e^{3}(e+2)(a+1)^{2}+1-o^{2}

0=(a^{2}-1)y^{2}+1-x^{2}

0=16r^{2}y^{4}(a^{2}-1)+1-u^{2}

0=n+l+v-y

0=(a^{2}-1)l^{2}+1-m^{2}

0=ai+k+1-l-i

0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}

0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m

0=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x

0=z+pl(a-p)+t(2ap-p^{2}-1)-pm.

对于这个方程组的所有正整数解：(a,b,...,z)，k + 2都是素数。可以把这个公式改写成多项式的形式：将14个等式记作p₁，p₂，……，p₁₄，那么可以说，多项式 $(k+2)(1-p_{1}^{2}-p_{2}^{2}-\cdots -p_{14}^{2})$ 的输入值(a,b,...,z)是正整数时，其值域的正值部分就是所有素数。

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

带高斯符號的素数公式

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

Mills公式

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

[A^{3^{n}}\;]

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