Crible d'Eratosthène

Présentation de l'algorithme.

Quelques rappels d'arithmétique.

Soient \(a\) et \(b\) deux entiers naturels. La relation binaire définie sur \({\mathbf N}\) par \begin{equation} a\mid b\quad\Leftrightarrow\quad\exists q\in{\mathbf N},\ aq=b \end{equation} est une relation d'ordre appelée relation de divisibilité. Si \(a\mid b\), on dit que \(a\) divise \(b\) ou que \(a\) est un diviseur de \(b\). Un entier naturel \(N\) est dit premier s'il admet exac­te­ment deux diviseurs distincts. Il y a une infinité de nombres premiers. En effet, s'il n'y en avait qu'un nombre fini \(n\), notons les \(p_1,\ p_2,\ldots, p_n\), le reste de la division euclidienne du nombre \[p_1p_2\ldots p_n+1\] par l'un quelconque des \(p_i\) est égal à 1 d'après le théorème de la division euclidienne, prouvant ainsi qu'il s'agit d'un nombre premier différent de tous les \(p_i\), ce qui est absurde. En arithmétique on dé­si­gne généralement par \((p_k)_{k\geq 1}\) la suite croissante des nombres premiers, i.e. \[p_1=2,\ p_2=3,\ p_3=5,\ p_4=7,\ p_5=11,\ldots\]

Nous aurons besoin du théorème fondamental de l'arithmétique :
Soit \(N\) un entier naturel, \(N\geq 2\). Alors \(N\) se décompose de manière unique comme un produit de facteurs premiers croissants dans l'ordre des facteurs : \begin{equation}\label{eq:arith} \exists k\in{\mathbf N},\quad n=\prod_{i=1}^kp_i^{r_i}, \end{equation} où les \(k\) nombres \(r_i\) sont des entiers strictement positifs.
L'écriture (\ref{eq:arith}) s'obtient aisément une fois que l'on aura montré que \(n\) s'écrit comme un produit de nombres premiers (pas nécessairement distincts). Il suffit alors d'ordonner ces nombres dans l'ordre croissant, ce qui est possible puisque l'ordre naturel est un ordre total. Si \(n\) est premier, il n'y a rien à montrer, sinon \(n\) admet au moins un diviseur dans l'intervalle \([1,n]\) et on note \(d\) le plus petit de ces diviseurs. Alors \(d\) est nécessairement premier, sans quoi il ne pourrait être le plus petit diviseur de \(n\). On note alors \(p_1\) ce diviseur premier de \(n\) et on reprend le même raisonnement avec l'entier \(n_1 = n/ p_1\). Par récurrence, on obtient ainsi une suite décroissante d'entiers et on s'arrête dès que \(n_i\) est premier.

Rien dans cette décomposition ne permet d'affirmer qu'elle est unique. Supposons qu'il existe des entiers naturels admettant plusieurs décompositions en produits de facteurs premiers, et soit \(n\) le plus petit d'entre eux. On note \begin{equation*} n=p_1p_2p_3\ldots p_k\quad\text{et}=\quad n=q_1q_2q_3\ldots q_l \end{equation*} deux décompositions différentes de \(n\) en supposant que les facteurs \(p_i\) sont rangés dans l'ordre croissant, ainsi que les \(q_j\). S'il existait deux premiers \(p_i\) et \(q_j\) égaux, alors l'entier \(n/p_i=n/q_j\), strictement inférieur à \(n\), admettrait deux décompositions distinctes ce qui est impossible puisque \(n\) était le plus petit. Comme \(n\geq p_1^2\) et \(n\geq q_1^2\) et que \(p_1\not=q_1\), alors \(n>p_1q_1\). D'autre part, \(p_1|n\) et \(q_1|n\) donc \(p_1q_1|n\) soit \(q_1|\frac{n}{p_1}\). Comme \(n/p_1< n \), il n'admet qu'une décomposition \(p_2p_3\ldots p_k\), ainsi \(q_1\) est l'un des \(p_i\) ce qui n'est pas possible.
Montrez que les nombres premiers sont les éléments minimaux de \({\mathbf N}\setminus\{1\}\) pour la relation de divisibilité. Quel est le plus petit élément s'il existe, le plus grand s'il existe ?
Soit \(n\geq 1\). En notant \(P_n:=1+\prod_{i=1}^np_i\), quelle est la plus petite valeur de \(n\) telle que \(P_n\) n'est pas un nombre premier. Quel est la décomposition en produit de facteurs premiers de ce \(P_n\) ?

La particularité de ces nombres engendre une multitude de nouvelles questions. Quelle est leur densité, c'est-à-dire quelle est la proportion de nombres premiers plus petits qu'une valeur fixée ? Comment sont-ils répartis ? Peut-on trouver une formule fermée qui fournit le \(n\)-ème nombre premier, ce qui signifie en terme de complexité que l'on est en mesure de calculer \(p_n\) en un temps po­ly­no­mial en la taille de \(n\) ? On va s'attacher pour commencer à présenter une méthode qui permet de les trouver.

Le crible.

Eratosthène était un savant grec, à la fois mathématicien, géographe, astronome et poète et qui dirigeait la grande bibliothèque d'Alexandrie deux siècles et demi avant jc. Il avait, entre autres, estimé la circonférence de la Terre. Il est passé à la postérité grâce à la méthode du crible qui porte son nom et qui permet d'obtenir la listes de tous les nombres premiers inférieurs à une valeur fixée.

Le principe du crible est simple. On se donne un entier \(N\) arbitraire et on constitue initialement la liste des entiers compris entre \(1\) et \(N\). L'algorithme consiste à cocher (cribler) tous les nombres qui ne sont pas premiers de la manière suivante :

  1. On se place au début de la liste et on crible 1 ;
  2. On avance jusqu'au prochain nombre \(p\) qui n'a pas été criblé (donc 2 initialement) ;
  3. On crible ses multiples, i.e. on coche tous les nombres \(kp\) pour tout \(k\in[2,\lfloor\frac{N}{p}\rfloor]\) ;
  4. On recommence au point 2 tant qu'on n'a pas atteint la fin de la liste.
Nous verrons un peu plus loin comment apporter quelques améliorations à cet algorithme, no­tam­ment en arrêtant le processus de crible dès que \(p>\sqrt{N}\).

L'illustration de l'algorithme conformément à la méthode qui a été employée manuellement par Era­tos­thè­ne en rangeant les nombres dans une table est bien plus parlante. Saisissez la valeur de l'entier \(N:=\).

Crible d'Eratosthène pour la valeur \(N=\) .

L'algorithme n'est plus qu'une simple réécriture de cette procédure dans notre pseudo-langage al­go­rithmi­que. Les cellules du tableau de booléen EstPremier sont initialisées à vrai sauf la première cellule. Pour faciliter la lecture et l'analyse du crible général, on déporte dans l'algorithme auxiliaire Multiples le crible de tous les multiples d'un nombre premier \(p\) particulier. On suppose que \(N\geq 1\) : 

Multiples(p,N)
données
   p,N: entiers
variables
   k: entier
debut
   k ← 2; cf. Lemme 3
   TQ (k ≤ N//p) FAIRE
       EstPremier[k * p] ← faux
       k ← k + 1
   FTQ   
fin

Cribler(N):tableau de booléens
données
   N: entier
variables
   EstPremier: tableau de booléens
   p,k: entiers
DEBUT
   p ← 1
   TQ p ≤ N FAIRE
      EstPremier[p] ← vrai
   FTQ
   EstPremier[1] ← faux
   p ← 2 cf. Lemme 4
   TQ (p ≤ N) FAIRE cf. Lemme 2
      Multiples(p,N)
      p ← p + 1   cf. Lemme 4 
      TQ (p ≤ N) ET NON(EstPremier[p]) FAIRE cf. Lemme 2
         p ← p + 1   cf. Lemme 4
      FTQ
   FTQ
   RENVOYER EstPremier
FIN
Le tableau EstPremier est un vecteur ca­rac­té­ris­ti­que, il code l'ensemble des nombres en­tiers \(k\) tels que EstPremier(\(k\)) est vrai. Par abus de langage on dira que le tableau contient l'entier \(k\) si la cellule d'indice \(k\) contient la valeur vrai.

La preuve de la validité de l'algorithme Multiples est laissée au lecteur. L'algorithme Cribler s'arrête. En effet la première boucle interne à la ligne #15 s'arrête puisqu'elle est conditionnée par la valeur de \(p\) qui doit rester bornée par l'entier \(N\) et qui est incrémentée à chaque passage. Le raisonnement est le même pour la deuxième boucle interne à la ligne #19 avec la variable \(k\) et la borne \(N/2\). Par conséquent la boucle externe à la ligne #14 s'arrête également pour la même raison, \(p\) étant in­cré­men­té au moins une fois à la ligne #16.

Nous allons prouver qu'à la fin de l'exécution de l'algorithme, le tableau code exactement tous les nombres premiers inférieurs à \(N\). On note \(\pi_n\) la \(n\)-ème valeur de la variable \(p\) à l'entrée de la boucle principale à la ligne #14.

À la \(n\)-ème entrée dans la boucle de la ligne #14 le tableau ne contient que des valeurs qui ne sont divisibles par aucun des nombres premiers \(p_i < p_n\) et \(\pi_n=p_n\).
Montrons le lemme par récurrence sur \(n\). C'est vrai pour \(n=1\). En effet, après l'initialisation du tableau, \(\pi_1=p=2\) et le tableau ne contient que \(2\).

D'après l'hypothèse de récurrence, \(\pi_n=p_n\) et après l'application de l'algorithme Multiples à la ligne #15, les indices \(k > p_n\) des cellules de valeur vrai ne sont divisibles par aucun des nombres premiers \(p_i\) tels que \(p_i\leq p_n\). La première cellule vrai après la cellule \(p_n\) a donc pour indice le nombre premier suivant \(p_{n+1}\). Elle est obtenue par l'instruction #16 et la boucle de la ligne #17.
Dans l'algorithme Cribler, on peut remplacer les conditions d'arrêt \(\color{#FF0}p\leq N\) de la boucle principale à la ligne #14 et de la boucle à la ligne #17 par la condition \(\color{#FF0}p\leq \sqrt{N}\).
Soit \(a\) un entier, \(a\in[2,N]\). Supposons que \(a\) soit criblé par un nombre premier \(p\) tel que \(p > \sqrt{a}\), alors \(a\) est un multiple de \(p\), il existe donc \(k\in{\mathbf N}\) tel que \(kp=a\). On a nécessairement \(k < \sqrt{a} < p\) sans quoi \(kp>a\). D'après le théorème fondamental de l'arithmétique, \(k\) se décompose en produit de facteurs premiers \(p_i\leq k\) tels que \(p_i < p\). Comme l'al­go­ri­thme crible les valeurs de la table avec la suite croissante des nombres premiers, \(a\) a né­ces­sai­re­ment déjà été criblé par un \(p_i < p\).
Dans l'algorithme Multiples, on peut commencer à cribler à partir de l'entier \(\color{#46F}k=p\) (ligne #7).
Soit \(kp\) un multiple de \(p\) avec \(k < p\). Le nombre \(k\) se décompose de manière unique comme un produit de facteurs premiers et notons \(q\) un de ses facteurs, donc il existe \(k'\) tel que \(k=q.k'\). Comme \(q < p\), l'algorithme a déjà criblé les multiples de \(q\), en particulier le multiple \((k'p).q=kp\).
Dans l'algorithme Cribler, on peut commencer le crible avec \(\color{#8A8}p\leftarrow 3\) et incrémenter de deux en deux \(\color{#8A8}p\leftarrow p+2\) (lignes #16 et #18).
C'est évident, en prétraitant le cas \(p=2\), et en commençant à \(p=3\) on peut avancer de deux en deux puisque tous les nombres premiers suivants sont impairs.

Complexité.

La taille \(n\) de la donnée à traiter est, comme toujours quand il s'agit de traiter des nombres, le nombre de ses chiffres dans une base \(b\) arbitraire et on rappelle que \begin{equation}\label{eq:digits} n = \lfloor\log_b N\rfloor + 1 \end{equation} que l'on résume en \(n=\Theta(\log N)\). Pour l'instant on commence l'évaluation avec \(N\) et pour ne pas compliquer inutilement les calculs, nous supposerons que l'algorithme crible à partir de \(p=2\). Analysons globalement le coût des opérations effectuées par l'algorithme Multiples. Pour tous les nombres premiers \(p_i\) tels que \(p_i\leq\sqrt{N}\), l'algorithme crible tous les multiples \(kp_i\) de \(p_i\) à partir de \(k=p_i\), le coût unitaire étant \(\Theta(1)\). On note \(C_N\) le nombre total de fois où l'algorithme crible une cellule. On a \begin{align} C_N&=\sum_{\overset{p\leq\sqrt{N}}{p\ \text{premier}}}\sum_{k=p}^{\lfloor\frac{N}{p}\rfloor}\Theta(1)\\ &=\Theta(1)\sum_{\overset{p\leq\sqrt{N}}{p\ \text{premier}}}\left(\lfloor\frac{N}{p}\rfloor-p+1\right)\\ &\leq\Theta(1)\sum_{\overset{p\leq\sqrt{N}}{p\ \text{premier}}}\lfloor\frac{N}{p}\rfloor\\ &\leq\Theta(N){\color{#FF0}\sum_{\overset{p\leq\sqrt{N}}{p\ \text{premier}}}\frac{1}{p}}\label{eq:start} \end{align}

Pour continuer ce calcul, nous aurons besoin du résultat suivant qui n'est pas tout à fait élémentaire et qui fournit une estimation de la somme partielle de la série des inverses des nombres premiers :

Soit \(N\) un entier naturel. Alors \begin{equation}\label{eq:lnln} {\color{#FF0}\sum_{\overset{p\leq N}{p\ \text{premier}}}\frac{1}{p}}=\Theta(\ln\ln N) \end{equation}

On peut reprendre le calcul de \(C_N\)  à partir de l'expression \((\ref{eq:start})\) en appliquant \((\ref{eq:lnln})\) et conclure avec \((\ref{eq:digits})\) : \begin{align} C_N&=O(N\ln\ln N)\\ &=O(e^n\ln n) \end{align}

Il nous reste à intégrer le coût de la construction du tableau et de la recherche du prochain nombre premier pour les différents appels à l'algorithme Multiples. La construction coûte \(\Theta(e^n)\) et on balaie la moitié des cellules de la table pour chercher à chaque fois le prochain nombre premier, l'incrément se faisant de deux en deux. Au final on obtient
La fonction de complexité du crible d'Eratosthène pour l'entier naturel \(N\) est \begin{equation} T(n)=O(e^n\ln n) \end{equation} où \(n\) désigne le nombre de chiffres de \(N\) dans une base arbitraire.

La conclusion de cette étude est que l'algorithme d'Eratosthène est malheureusement impraticable pour trouver des nombres premiers de grande taille. Pour dépasser cette limite, on utilise d'autres algorithmes, comme l'algorithme de Solovay-Strassen ou l'algorithme de Rabin-Miller qui permettent tout deux de tester si un nombre est premier ou pas. Le principe général est sensiblement le même pour les deux algorithmes, on tire les bits d'un entier \(N\) au hasard puis on lui fait passer une série de tests, à chaque fois que le test est satisfait, la probabilité que l'entier \(N\) soit premier augmente. On arrête les tests dès que l'on considère que cette probabilité est suffisamment élevée. Un nombre \(N\) qui passe de tels test n'est donc pas nécessairement premier, on parle dans ce cas de nombre pseudo-premier.
On définit la fonction \(\pi:{\mathbf R}\rightarrow{\mathbf R}\) par \begin{equation} \pi(x):=\#\{p\in{\mathbf N}\mid p\ \text{premier}\} \end{equation}

Un premier résultat donne une indication sur la répartition des nombres premiers. Il s'agit du théorème des nombres premiers :

Le nombre \(\pi(x)\) est asymptotiquement équivalent au quotient \(\frac{x}{\ln x}\), i.e. \begin{equation}\label{eq:lim} \lim_{x\rightarrow\infty}\pi(x)\frac{\ln x}{x}=1 \end{equation}
Un corollaire de ce théorème est le théorème de raréfaction des nombres premiers, en effet d'après \((\ref{eq:lim})\), on déduit \begin{equation} \lim_{n\rightarrow\infty}\frac{\pi(n)}{n}=0. \end{equation} On peut fournir également un encadrement du \(n\)-ème nombre premier \(p_n\) :
Pour tout entier \(n\geq 2\), on a \begin{equation}\label{eq:bornes} \frac{n\ln n}{6\ln 2}\leq p_n\leq \frac{8n\ln n}{\ln 2} \end{equation}

Travaux pratiques

Écrivez un programme qui renvoie la liste de tous les nombres premiers inférieurs à un entier \(N\) fourni en appliquant l'algorithme Cribler. Tracez la courbe de la fonction définie par \[N\mapsto\frac{\pi(N)}{N}\] Pour les valeurs de \(N\) que vous aurez été en mesure de calculer. Calculez de manière empirique la somme des inverses des nombres premiers de cette liste et comparez cette valeur avec celle fournie en \((\ref{eq:digits})\) en traçant encore une fois une courbe.

Tracez sur un même graphique les courbes des trois fonctions définies par les trois expressions des inégalités \((\ref{eq:bornes})\).