Il est convenu de distinguer plusieurs types de démonstrations mathématiques, en fonction du degré de sophistication des théories mathématiques auxquelles on fait appel ; le théorème des nombres premiers fournit un prototype pour ce genre de considérations.
On a longtemps cru, au début du XXe siècle, et notamment G. H. Hardy, que toute démonstration du théorème des nombres premiers devait forcément faire appel à des théorèmes d'analyse complexe ; ce qui par ailleurs pouvait paraître frustrant pour un énoncé semblant porter essentiellement sur les nombres entiers (quoique nécessitant les nombres rationnels, voire les nombres réels pour pouvoir être énoncé). C'était donc un défi pour les mathématiciens d'essayer de trouver une démonstration élémentaire de ce théorème - élémentaire ne voulant pas dire simple, ni peu sophistiquée, mais seulement faisant le moins possible appel à des méthodes externes, à l'arithmétique dans notre cas - ou bien de comprendre précisément pourquoi certains énoncés ne sont accessibles qu'avec des méthodes plus évoluées que ce à quoi on pouvait s'attendre. Hardy parlait donc de « profondeur » des théorèmes et pensait que le théorème des nombres premiers faisait partie des énoncés dont la « profondeur » ne les rendait accessibles que par le biais de l'analyse complexe.
Une première brèche dans cette conception fut la découverte d'une démonstration basée seulement sur le théorème taubérien de Norbert Wiener ; mais il n'était pas clair qu'on ne puisse pas attribuer à ce théorème une « profondeur » équivalente aux théorèmes issus de l'analyse complexe.
Le débat fut tranché en 1949, quand Paul Erdős et Atle Selberg donnèrent chacun une démonstration indéniablement élémentaire du théorème des nombres premiers. Quelle que soit la valeur du concept de « profondeur », celle du théorème des nombres premiers n'exigeait pas d'analyse complexe. De manière plus générale, la découverte de ces démonstrations élémentaires provoqua un regain d'intérêt pour les méthodes de crible, qui trouvèrent ainsi toute leur place dans l'arithmétique.
On commence par écrire l'égalité entre le produit d'Euler et la factorisation de Weierstrass de la fonction zêta :
avec s de partie réelle strictement supérieure à 1,
Grâce à la série entière complexe
pour Re(s) > 1. On veut maintenant intégrer cette égalité contre la fonction xs / s (avec x constante fixée). Le contour d'intégration est un rectangle de côté droit {Re(s) = σ} avec σ > 1 et qui s'étend à l'infini verticalement et à gauche. Après des calculs faisant appel au théorème des résidus, on obtient la célèbre formule explicite de Riemann, pour x > 0 non puissance d'un nombre premier :
avec cette fois ρ balayant seulement les zéros non triviaux de zêta (les triviaux ont été regroupés dans le dernier terme). A gauche on reconnaît la fonction de Tchebychev ψ(x), asymptotiquement équivalente à π(x) ln(x). Le théorème des nombres premiers est par conséquent presque démontré, puisqu'à droite on voit le terme x attendu. Le dernier point à montrer est que les autres termes de droite sont négligeables devant x, autrement dit qu'il n'y a pas de zéro ρ dont la partie réelle est 1. Ce point a été prouvé par Hadamard et De la Vallée Poussin.