Sin embargo, con el tiempo, muchos de estos resultados han sido reprobados utilizando solo técnicas elementales.
Este teorema fue probado por primera vez en 1896 por Jacques Hadamard y Charles-Jean de la Vallée Poussin utilizando análisis complejos.
Godfrey Harold Hardy expresó fuertes reservas; consideró que la "profundidad" esencial del resultado descartaba pruebas elementales:
Sin embargo, en 1948, Atle Selberg produjo nuevos métodos que lo llevaron junto con Paul Erdős a encontrar pruebas elementales del teorema del número primo.
Harvey Friedman conjeturó: "Todo teorema publicado en los Annals of Mathematics cuya declaración implica solo objetos matemáticos finitos (es decir, lo que los lógicos llaman una declaración aritmética) se puede probar en la aritmética elemental.