En mathématiques, la recherche de formules exactes donnant tous les nombres premiers, certaines familles de nombres premiers ou le n-ième nombre premier s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les principaux résultats obtenus.

L'espoir d'obtenir une formule exacte et simple donnant le n-ième nombre premier p_n, ou le nombre π(n) de nombres premiers inférieurs ou égaux à n, s'est très tôt heurté à l'extrême irrégularité de leur répartition, ce qui a amené à se contenter d'objectifs moins ambitieux. Mais même la recherche de formules ne donnant que des nombres premiers s'avère assez décevante ; ainsi, il est facile de montrer qu'il n'existe aucune fonction polynomiale non constante P(n) qui ne prendrait que des valeurs premières pour tous les entiers n, ou même pour presque tous les n^[1] ; en fait, on ignore même s'il existe un polynôme de degré > 1 qui prenne une infinité de valeurs premières^[2].

C'est ce qui explique l'intérêt de la remarque d'Euler : le polynôme quadratique P(n) = n² + n + 41 est premier pour tous les nombres entiers positifs strictement inférieurs à 40 (${\displaystyle P(40)=1681=41^{2}}$ et si n est un multiple de 41, P(n) sera lui aussi un multiple de 41, et donc non premier). D'ailleurs, 41 est le plus grand « nombre chanceux d'Euler », c'est-à-dire le plus grand entier A pour lequel le polynôme n² + n + A est premier pour tous les n strictement inférieurs à A – 1 ; cela résulte du théorème de Stark-Heegner, un résultat de la théorie des corps de classes qui n'a été démontré qu'en 1967. De manière similaire, d'autres formules polynomiales (de degré plus élevé) produisent des suites de nombres premiers. Ainsi, en 2010, l'une d'entre elles a permis d'établir un nouveau record : une suite de 58 nombres premiers^[3] :

${\displaystyle {\frac {1}{72}}n^{6}-{\frac {5}{24}}n^{5}-{\frac {1493}{72}}n^{4}+{\frac {1027}{8}}n^{3}+{\frac {100471}{18}}n^{2}-{\frac {11971}{6}}n-57347}$ est premier^[4] pour chaque entier n de –42 à 15.

D'autres formules utilisant des fonctions plus générales, telle celle de Mersenne, avaient été envisagées, la plus célèbre étant celle conjecturée par Fermat : F_n = 2²ⁿ + 1 est premier pour tout n. Hélas, si ces nombres (appelés désormais nombres de Fermat) sont bien premiers pour 0 ≤ n ≤ 4, Euler découvrit que le sixième, F₅, est divisible par 641, ruinant la conjecture ; actuellement, on pense au contraire que F_n est toujours composé dès que n > 4^[5]. Dans le même genre, la formule de Mills n'engendre que des nombres premiers, mais a l'inconvénient de n'être que théorique.

Des formules approchées donnant p_n ou π(n) ont été imaginées au XVIII^e siècle, culminant avec les conjectures de Legendre et Gauss. Si leur hypothèse la plus simple, ${\displaystyle \lim _{n\to +\infty }\pi (n)\ln n/n=1,}$ a été démontrée par Hadamard et La Vallée Poussin un siècle plus tard (c'est le théorème des nombres premiers), la difficulté du problème est bien montrée par le fait qu'une des conjectures de Gauss, plus précise, et majorant π(n) par ${\displaystyle {\rm {Li}}(n)=\int _{2}^{n}{\frac {\mathrm {d} x}{\ln x}}}$, qui paraissait fort plausible au vu des tables de ces deux fonctions, s'est cependant révélée fausse, mais seulement pour des valeurs de n gigantesques^[6].

Des résultats plus précis, et en particulier une bonne estimation du terme d'erreur h(n) dans la formule p_n = n ln n + h(n), font encore l'objet de conjectures (dépendant souvent de l'hypothèse de Riemann) ; parmi les meilleurs résultats vraiment démontrés, on peut citer l'encadrement suivant, déterminé par Dusart en 1999^[7] :

${\displaystyle n\left(\ln n+\ln \ln n-1\right)<p_{n}<n\left(\ln n+\ln \ln n-1/2\right).}$

Ces méthodes sont loin de donner des formules exactes ; par exemple, cet encadrement affirme seulement que le millième nombre premier, 7919, est compris entre 7840 et 8341.

Malgré les remarques précédentes, il est cependant possible d'obtenir des formules exactes d'apparence simple, mais sans intérêt pratique du fait de calculs trop longs.

Le théorème de Wilson permet facilement de montrer que la fonction f(n) = 2 + (2(n!) mod(n + 1)) produit tous les nombres premiers, et seulement eux, quand n parcourt tous les entiers positifs : f(n) = n + 1 si n + 1 est premier, et f(n) = 2 sinon^[8].

La factorielle de n prend rapidement des valeurs bien trop grandes pour être utilisable en pratique, mais le recours à la fonction modulo (que l'on sait calculer rapidement) contourne cette difficulté ; cependant, les seules méthodes connues pour calculer f(n) prennent environ n opérations élémentaires, de plus, cette fonction ne donne pas réellement π(n), mais teste seulement si n est premier ou non ; pour ce test, ou pour calculer π(n), f est donc beaucoup plus inefficace que la méthode de division par tous les entiers inférieurs ou égaux à √n (ou que le crible d'Ératosthène), méthodes elles-mêmes bien moins rapides que les meilleurs tests de primalité actuellement connus.

D'autres formules donnant directement p_n ou π(n) peuvent être construites à partir de f ; ainsi, on a, en utilisant la fonction partie entière ⌊∙⌋ :

${\displaystyle \pi (n)=\sum _{j=2}^{n}\left\lfloor {(j-1)!+1 \over j}-\left\lfloor {(j-1)! \over j}\right\rfloor \right\rfloor }$ ;

mais ces formules sont encore moins facilement utilisables que celle donnant f.

Une autre approche, plus prometteuse et n'utilisant pas le théorème de Wilson, consiste essentiellement à simuler le crible d'Ératosthène, ou les formules qu'on peut en déduire, comme la formule d'inclusion-exclusion de Legendre^[9] ; c'est le terrain de prédilection de nombreux amateurs, ainsi, les formules suivantes ont été déterminées en 2000 par un enseignant espagnol, S. M. Ruiz^[10]  :

${\displaystyle \pi (n)=n-1+\sum _{j=2}^{n}\left[{2 \over j}\left(1+\sum _{s=1}^{\left\lfloor {\sqrt {j}}\right\rfloor }\left(\left\lfloor {j-1 \over s}\right\rfloor -\left\lfloor {j \over s}\right\rfloor \right)\right)\right]}$

et

${\displaystyle p_{n}=1+\sum _{k=1}^{2(\lfloor n\ln(n)\rfloor +1)}\left(1-\left\lfloor {\pi (k) \over n}\right\rfloor \right).}$

On remarquera le nombre important de sommations dans ces formules, qui fait qu'elles seraient, elles aussi, peu utilisables en pratique ; de bien meilleures méthodes de calcul exact de π(n) et p_n, qu'on trouvera détaillées dans l'article consacré à ces fonctions, restent d'ailleurs relativement inefficaces^[12].

Compte tenu des remarques de la première section, l'existence de polynômes à plusieurs variables ne prenant que des valeurs premières paraissait peu vraisemblable. Aussi, les travaux de Youri Matiiassevitch, qui a résolu en 1970 le dixième problème de Hilbert en montrant que toute relation diophantienne pouvait être codée par un tel polynôme, provoquèrent une véritable surprise. Il est même possible de donner des exemples explicites de ce résultat ; ainsi, le monstrueux polynôme suivant (de degré 25, et comportant 26 variables)^[13] :

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

avec

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

${\displaystyle \alpha _{1}=(gk+2g+k+1)(h+j)+h-z}$

${\displaystyle \alpha _{2}=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}}$

${\displaystyle \alpha _{3}=2n+p+q+z-e}$

${\displaystyle \alpha _{4}=e^{3}(e+2)(a+1)^{2}+1-o^{2}}$

${\displaystyle \alpha _{5}=(a^{2}-1)y^{2}+1-x^{2}}$

${\displaystyle \alpha _{6}=16r^{2}y^{4}(a^{2}-1)+1-u^{2}}$

${\displaystyle \alpha _{7}=n+l+v-y}$

${\displaystyle \alpha _{8}=(a^{2}-1)l^{2}+1-m^{2}}$

${\displaystyle \alpha _{9}=ai+k+1-l-i}$

${\displaystyle \alpha _{10}=[(a+u^{2}(u^{2}-a))^{2}-1](n+4dy)^{2}+1-(x+cu)^{2}}$

${\displaystyle \alpha _{11}=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m}$

${\displaystyle \alpha _{12}=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x}$

${\displaystyle \alpha _{13}=z+pl(a-p)+t(2ap-p^{2}-1)-pm}$

a, pour ensemble de valeurs strictement positives (lorsque ${\displaystyle (a,\dots ,z)\in \mathbb {N} ^{26}}$), exactement l'ensemble des nombres premiers^[14].

Mais on peut cependant se demander s'il s'agit bien là encore d'une « formule ». Il est d'ailleurs extrêmement difficile de trouver un jeu de 26 variables donnant un nombre positif, et il n'existe aucune méthode connue pour résoudre un tel système autrement que par l'exploration de toutes les combinaisons possibles des paramètres.

Bien qu'on ne puisse pas parler exactement de formule, une suite définie par une relation de la forme u_n+1 = f(u_n), où f est une fonction assez simple, et qui ne prendrait que des valeurs premières, resterait intéressante. Certaines suites dérivées de la démonstration d'Euclide de l'infinité des nombres premiers (comme la suite de Sylvester) s'avèrent décevantes à cet égard, ainsi on ne sait même pas s'il existe une infinité de nombres premiers primoriels. On ne connaît en fait que peu d'exemples intéressants de telles suites, d'ailleurs d'une forme un peu plus complexe.

Conway a ainsi défini une généralisation du problème de Syracuse, qui le transforme en un langage de programmation, FRACTRAN ; le texte suivant^[15] :

${\displaystyle {\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{14}},{\frac {15}{2}},{\frac {55}{1}}.}$

correspond, pour ce langage, à un programme qui produit, dans l'ordre, la suite des nombres premiers (on peut donc l'interpréter comme une suite définie par récurrence). Pour cela, partant du nombre 2, on multiplie itérativement par la première fraction donnant un produit entier. Parmi la suite d'entiers qu'on obtiendra, les puissances de 2 successives auront pour exposant la suite des nombres premiers. L'efficacité de ce programme étant extrêmement faible, l'intérêt est seulement dans l'élégance de son écriture.

La suite u_n définie par la relation de récurrence

${\displaystyle a_{n}=a_{n-1}+\operatorname {gcd} (n,a_{n-1}),\quad a_{1}=7,}$

(où gcd(x, y) désigne le PGCD de x et y) et u_n = a_n+1 – a_n commence par 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, ... (suite A132199 de l'OEIS). Rowland a démontré en 2008 que cette suite ne contient (à part 1) que des nombres premiers^[16].

En 1947, William H. Mills a montré qu'il existe des nombres réels M tels que pour tout entier n, la partie entière de M⁽³ⁿ⁾ est un nombre premier^[17]. Le plus petit M ayant cette propriété, la constante de Mills, est d'ailleurs connu avec une bonne précision, mais qui s'avère tout aussi illusoire pour calculer de grands nombres premiers, par exemple parce que la taille de p(n) = ⌊M⁽³ⁿ⁾⌋ devient rapidement bien supérieure à tout ce qu'un ordinateur peut contenir (pour stocker p(25), on a déjà besoin d'un téraoctet).

En 2017, Fridman et al. ont démontré^[18] que la suite de réels (f_n) définie par :

• ${\displaystyle f_{1}=\sum _{k=1}^{\infty }{\frac {p_{k}-1}{p_{k-1}\#}}=\sum _{k=1}^{\infty }{\frac {p_{k}-1}{\prod _{i=1}^{k-1}p_{i}}}}$
• ${\displaystyle \forall n\geq 1\quad f_{n+1}=\lfloor f_{n}\rfloor \left(f_{n}-\lfloor f_{n}\rfloor +1\right)}$

vérifie :

${\displaystyle \forall n\geq 1\quad p_{n}=\lfloor f_{n}\rfloor }$.

L'irrationnel f₁ = 2,9200509773…^[19] n'est autre^[20] que la valeur moyenne de la suite 2, 3, 2, 3, 2, 5, etc. dont le n-ième terme est le plus petit nombre premier ne divisant pas n^[18],[21].

Bien que les calculs correspondants soient plus maniables que ceux de la formule de Mills, ce résultat reste tout aussi théorique. En effet, ces calculs nécessitent de connaître un nombre de plus en plus important de décimales de f₁ (environ n décimales pour obtenir p_n)^{[réf. souhaitée]}, mais pour obtenir n décimales de f₁, il faut déjà connaître les valeurs des n premiers nombres premiers^{[réf. souhaitée]}. Par contre, cela procure une compression mémoire, en effet, le stockage de ${\displaystyle n}$ décimales nécessite moins de mémoire que pour les ${\displaystyle n}$ premiers nombres premiers.

La notion de fraction continue permet de définir le nombre réel positif ${\displaystyle u_{1}=[p_{1},p_{2},p_{3},...]=2.31303673643...}$  A064442 à partir duquel on retrouve la suite des nombres premiers en utilisant la récurrence suivante: ${\displaystyle u_{n+1}=(u_{n}-\lfloor u_{n}\rfloor )^{-1}}$. Il s'ensuit que ${\displaystyle p_{n}=\lfloor u_{n}\rfloor }$.

La méthode de Fridman et al. peut être vue comme une alternative de la méthode par fraction continue (connue antérieurement), et on peut donc émettre la même réserve : le nombre ${\displaystyle u_{1}}$ est défini (ci-dessus) en utilisant les nombres premiers, il faudrait donc une définition alternative indépendante des nombres premiers pour que cette méthode soit utilisable.

• Jean-Paul Delahaye, Merveilleux nombres premiers : Voyage au cœur de l'arithmétique, 2000 [détail de l’édition]
• Marcus du Sautoy (trad. de l'anglais), La Symphonie des nombres premiers, Paris, éditions Héloïse d'Ormesson, 2005, 491 p. (ISBN 2-35087-011-1)

(en) Eric W. Weisstein, « Prime Formulas », sur MathWorld

v · m Nombres premiers
Donnés par une formule	combinatoire factoriel (n!±1) primoriel (pn#±1) Euclide (pn#+1) polynomiale Pythagore (4n + 1) cubain (x3 − y3)/(x − y) quatrain (x4 + y4) exponentielle Fermat (22n + 1) Mersenne (2p – 1) Double de Mersenne (22p–1 –1) Pierpont (2u3v + 1) Carol ((2n – 1)2 – 2) Kynea ((2n + 1)2 – 2) Thebit (3·2n – 1) Wagstaff ((2p + 1)/3) Proth (k2n + 1) Cullen (n2n + 1) Woodall (n2n – 1) Mills (⌊A3n⌋)
Appartenant à une suite	Fibonacci Lucas Motzkin Bell Pell Perrin Newman-Shanks-Williams
Ayant une propriété remarquable	bon chanceux fortuné Higgs illégal Pillai Ramanujan régulier Stern super supersingulier Wall-Sun-Sun Wieferich Paire de Wieferich Wilson Wolstenholme
Ayant une propriété dépendant de la base	diédral palindrome Reimerp répunit (10n − 1)/9 permutable circulaire délicat tronquable minimal long unique Smarandache-Wellin partie entière de puissances de constante troncature de constante
Propriétés mettant en jeu plusieurs nombres	singleton Chen {p ; p+2 premier ou semi-premier} équilibré (faible, fort) {pn ; pn = (<, >) (pn–1 + pn+1)/2} Sophie Germain {p ; 2p + 1 premier} sûr {p ; (p – 1)/2 premier} n-uplet jumeaux (p, p + 2) cousins (p, p + 4) sexy (p, p + 6) triplet (p, p + 2 ou p + 4, p + 6) quadruplet (p, p + 2, p + 6, p + 8) quintuplet (p – 4, p, p + 2, p + 6, p + 8) ou (p, p + 2, p + 6, p + 8, p + 12) sextuplet (p – 4, p, p + 2, p + 6, p + 8, p + 12) suite progression arithmétique (p + an) chaîne de Cunningham (p, 2p ± 1, etc.)
Classement par taille	titanesque (1 000+ chiffres) gigantesque (10 000+) méga (1 000 000+) record
Généralisations (entier quadratique)	Eisenstein Gauss
Nombre composé	pseudo-premier presque premier semi-premier interpremier
Nombre connexe	probable (NPP)
Test de primalité	Crible d'Ératosthène Test de Fermat Test de Lucas-Lehmer Test de Lucas-Lehmer pour les nombres de Mersenne Test de Pépin Test de Miller-Rabbin Test de Solovay-Strassen Test AKS
Conjectures et théorèmes de théorie des nombres	Conjecture d'Agoh-Giuga Conjecture d'Artin Conjecture de Bateman-Horn Conjecture de Bouniakovski Conjecture de Brocard Conjecture de Cramér Conjecture de Dickson Conjecture d'Elliott-Halberstam Conjecture de Firoozbakht Conjecture de Goldbach forte faible Conjecture de Grimm Conjecture de Hardy-Littlewood première seconde Conjecture de Legendre Conjecture de Lemoine Conjecture des nombres premiers de Waring Conjecture d'Oppermann Conjecture de Polignac Conjecture de Redmond-Sun Fonction de compte des nombres premiers Formules pour les nombres premiers Hypothèse H de Schinzel Nouvelle conjecture de Mersenne Théorème de Green-Tao Théorème des nombres premiers Théorème de la progression arithmétique Théorème de Rosser Théorème de Vinogradov
Constantes liées aux nombres premiers	Constante de Brun Constante de Legendre Constante de Mills Constante des nombres premiers Constante de Copeland-Erdős
Prime Pages Liste de nombres premiers Liste de suites de nombres premiers

• Arithmétique et théorie des nombres