En matemáticas, una fórmula de los números primos es aquella que genera los números primos, exactamente y sin excepción alguna. Otra gran cuestión es qué se considera como una «fórmula» y lo que no. No existe ninguna fórmula polinómica para obtener todos los números primos. Tampoco existe alguna fórmula polinómica no constante que solo genere valores primos. La mayoría de la gente puede objetar que el término «fórmula» se restringe solamente a los polinomios. ¿Podrían usarse sumatorias, factoriales y la función piso? Si así fuera, de hecho, sí existen fórmulas para obtener números primos. Una interpretación razonable de la palabra «fórmula» es «una máquina de Turing que se detiene bajo todas las entradas». Bajo esta interpretación ciertamente existen máquinas de Turing que se detienen, capaces de computar el enésimo número primo. Aun así, nadie sabe cómo calcular el enésimo número primo en tiempo polinómico. Dicho de otra forma, no se conoce alguna fórmula fácilmente computable.

Se sabe que no existe una función polinómica no constante ${\displaystyle P(n)\,\!}$ que evalúe números primos para todos los enteros n. La comprobación a esto es simple: Supongamos que dicho polinomio existe. Entonces ${\displaystyle P(1)\,\!}$ evaluaría al primo p, entonces ${\displaystyle P(1)\equiv 0{\pmod {p}}}$. Para cualquier k, ${\displaystyle P(1+kp)\equiv 0{\pmod {p}}}$, así que ${\displaystyle P(1+kp)\,\!}$ no puede ser primo (si lo fuera, sería divisible por p) a menos que fuera el mismo p. La única forma en que ${\displaystyle P(1+kp)=P(1))\,\!}$ para toda k es si la función polinómica es constante.

Si aplicamos más la teoría de los números algebraicos, se puede mostrar un resultado aún mayor: no existe una función polinómica no constante P(n) que evalúe a un número primo para casi todos los enteros n.

El polinomio cuadrático

${\displaystyle P(n)=n^{2}+n+41\,\!}$

devuelve números primos para todos los enteros no negativos menores que 40. Los números primos para ${\displaystyle n=0,1,2,3...\,\!}$ son ${\displaystyle 41,43,47,53...\,\!}$. Las diferencias entre los términos son ${\displaystyle 2,4,6,8,10...\,\!}$. Para ${\displaystyle n=40\,\!}$, se produce un número cuadrado, ${\displaystyle 1681\,\!}$, el cual es igual a ${\displaystyle 41\cdot 41}$, el menor número compuesto para esta fórmula. De hecho si 41 divide a n, también divide a ${\displaystyle P(n)\,\!}$. El fenómeno se relaciona con la espiral de Ulam, la cual también es implícitamente cuadrática.

Basándonos en el teorema de Dirichlet sobre las progresiones aritméticas se sabe que funciones lineales ${\displaystyle f(x)=ax+b\,\!}$ producen infinitos números primos siempre y cuando a y b sean primos relativos (aunque tal función no asumirá valores primos para cualquier x).

No se conoce si existe un polinomio invariable de al menos grado mayor que 2 que genere un número infinito de valores que son primos.

Un conjunto de ecuaciones diofánticas en 26 variables puede ser usada para obtener números primos. Jones demostró que dado un número ${\displaystyle k+2\,\!}$ éste es primo si y solo si el siguiente sistema de 14 ecuaciones diofánticas tiene una solución en los números naturales:^[1]​

${\displaystyle 0=wz+h+j-q}$

${\displaystyle 0=(gk+2g+k+1)(h+j)+h-z\,\!}$

${\displaystyle 0=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}\,\!}$

${\displaystyle 0=2n+p+q+z-e\,\!}$

${\displaystyle 0=e^{3}(e+2)(a+1)^{2}+1-o^{2}\,\!}$

${\displaystyle 0=(a^{2}-1)y^{2}+1-x^{2}\,\!}$

${\displaystyle 0=16r^{2}y^{4}(a^{2}-1)+1-u^{2}\,\!}$

${\displaystyle 0=n+l+v-y\,\!}$

${\displaystyle 0=(a^{2}-1)l^{2}+1-m^{2}\,\!}$

${\displaystyle 0=ai+k+1-l-i\,\!}$

${\displaystyle 0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}\,\!}$

${\displaystyle 0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m\,\!}$

${\displaystyle 0=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x\,\!}$

${\displaystyle 0=z+pl(a-p)+t(2ap-p^{2}-1)-pm\,\!}$

Esto puede ser usado para producir un polinomio que genere números primos. Denotemos los lados derechos de las ecuaciones de arriba por ${\displaystyle \alpha _{1},\alpha _{2},\cdots ,\alpha _{14}}$. Entonces:

${\displaystyle (k+2)(1-{\alpha _{1}}^{2}-{\alpha _{2}}^{2}-\cdots -{\alpha _{14}}^{2})}$

es un polinomio de 26 variables, y el conjunto de los números primos es idéntico al conjunto de los valores positivos tomados por este polinomio con los valores ${\displaystyle a,b,\cdots ,z}$ del rango sobre los enteros no negativos.

Un teorema general de Matiyasévich dice que si un conjunto se define como un conjunto de ecuaciones diofánticas, también puede ser definido como un sistema de ecuaciones diofánticas con sólo 9 variables. Por lo tanto, existe un polinomio que genera números primos como el anterior de tan sólo 10 variables. Sin embargo, el grado de dicho polinomio es muy grande (del orden de ${\displaystyle 10^{45}\,\!}$). Visto de otra manera, también podemos transformar dicho polinomio a grado 4, pero con 58 variables.

• Constante de Mills
• Número primo

• Weisstein, Eric W. «Prime Formulas». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.