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?
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.
que evalúe números primos para todos los enteros n. La comprobación a esto es simple: Supongamos que dicho polinomio existe.
no puede ser primo (si lo fuera, sería divisible por p) a menos que fuera el mismo p. La única forma en que
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 devuelve números primos para todos los enteros no negativos menores que 40.
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
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.
é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] Esto puede ser usado para producir un polinomio que genere números primos.
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.
Visto de otra manera, también podemos transformar dicho polinomio a grado 4, pero con 58 variables.