Le crible d’Ératosthène

Élaborer une méthode

Un nombre premier est un nombre entier naturel ayant la caractéristique de n’être divisible sans reste par aucun autre entier naturel que 1 et lui-même. Les nombres premiers sont répartis irrégulièrement parmi tous les nombres entiers naturels. C’est pourquoi ils fascinent les mathématiciens depuis des milliers d’années.

La suite de tous les nombres premiers compris entre 1 et n commence de la façon suivante :

2     3     5     7     11     13     17     19     23     29     31     37     41     …

De nombreuses problématiques dans lesquelles les nombres premiers jouent un rôle ont émergé au fil du temps. Toutes n’ont pas encore été résolues. En voici deux exemples :

En 1742, Christian Goldbach (1694-1764) a formulé une observation intéressante, connue sous le nom de conjecture de Goldbach :
Chaque nombre pair supérieur ou égal à 4 peut être représenté comme la somme de deux nombres premiers.
Nous trouvons par exemple : 4 = 2 + 2,     6 = 3 + 3,     8 = 3 +5,     10 = 3 + 7 = 5 + 5,     etc.

Pour que cela soit vrai, il suffit qu’il y ait au moins une possibilité de décomposition pour chaque nombre pair plus grand que 4. Il en existe même plusieurs pour la plupart de ces nombres. Le diagramme suivant a été réalisé à l’aide d’un tableau de nombres premiers et indique combien il y a de solutions. Sur l’axe des x se trouvent les nombres pairs à décomposer.

Lorsque le nombre n croît, le nombre de solutions augmente légèrement en moyenne. Lorsque n est très élevé, le diagramme prend une forme qui lui a valu le nom de comète de Goldbach. Aucun nombre pair plus grand que 4 n’a été trouvé pour lequel cette affirmation n’est pas vraie. Pourtant, jusqu’à présent, personne n’a proposé de démonstration prouvant qu’elle est valable pour tous.

Comète de Goldbach
Possibilités d’écrire le nombre n comme la somme de deux nombres premiers avec 4 ≤ n ≤ 10⁶ (Source : Wikipédia).

Carl Friedrich Gauss (1777-1855) a analysé la répartition des nombres premiers tout en les comptant. Il a étudié la fonction π(n), qui est égale à la quantité de nombres premiers entre 1 et n.

Voici un diagramme de cette fonction :

Pour des raisons évidentes, on constate que π(n) est une fonction en escalier. Gauss a construit une courbe « lisse » qui reste le plus proche possible de π(n) quelle que soit la valeur de n. Pour se faire une idée de la démarche à suivre et contrôler plus tard son résultat, il avait besoin d’un tableau de nombres premiers, c’est-à-dire de la suite des nombres premiers compris entre 1 et n.
Le problème du calcul de π(n) a été résolu depuis, mais entrer dans les détails serait ici hors sujet. Pour en savoir plus (en anglais).

Aujourd’hui, les nombres premiers ne sont plus seulement un défi pour les mathématiciens, mais ont une valeur pratique. Ainsi, les nombres premiers à 100 chiffres jouent un rôle central dans le cryptage électronique de données.

De l’idée à la réalisation

D’après les connaissances actuelles, le premier à avoir présenté un algorithme pour calculer les tableaux de nombres premiers était un savant grec de haut rang dans l’ancienne Alexandrie, Eratosthène de Cyrène (env. 276-194 avant JC). Il dirigeait la fameuse bibliothèque qui renfermait tout le savoir des temps anciens. Il traitait les questions essentielles de l’époque dans les domaines de l’astronomie, de la géologie et des mathématiques : Quelle est la circonférence de la terre ? D’où vient le Nil ? Comment peut-on construire un cube à partir d’un autre en faisant doubler le volume de ce dernier ?

Nous cherchons à comprendre comment il a développé une méthode efficace à partir d’une idée de base simple, qui, déjà à son époque, pouvait être exposée sur un papyrus ou sur du sable. Nous allons présenter successivement quatre méthodes, chacune apportant une amélioration à la précédente. Nous étudierons la rapidité de ces algorithmes dans la pratique pour calculer un grand tableau de nombres premiers, en prenant comme limite un milliard, soit n = 10⁹.

Animation interactive

L’animation interactive ci-dessous vous permettra de visualiser chacune des quatre méthodes en choisissant la valeur de n (jusqu’à n = 1000). Nous vous proposons pour commencer la valeur par défaut n = 100.

Pour les différentes valeurs de n, observez quelles sont les valeurs prises par i, k et i . k.

(Ne vous attendez pas à pouvoir comparer les temps de calcul d’une façon exacte avec cette applet. Néanmoins, vous constaterez que plus n est élevé, plus les différences sont importantes. Pour mieux voir le déroulement de l’algorithme, vous pouvez ajouter un temps d’arrêt (en ms) entre deux calculs consécutifs, par défaut 100 ms.)

Méthode de base : une idée simple

Par définition, un nombre m n’est pas un nombre premier si et seulement s’il existe deux nombres i et k tels que 2 ≤ i, k ≤ m et i . k = m. Nous pouvons utiliser cette égalité pour formuler un algorithme très simple afin de construire un tableau de nombres premiers :

Tableau de nombres premiers (méthode de base)
Écrire tous les nombres de 2 jusqu’à n dans une suite
Calculer tous les produits i . k où les nombres i et k sont compris entre 2 et n
Supprimer tous les résultats figurant dans la liste

On constate immédiatement que cette simple règle fait bien ce qui est attendu : tous les nombres qui sont encore dans la liste à la fin ne sont pas le résultat d’un des produits calculés. Ils ne peuvent donc pas être écrits comme un tel produit et sont donc des nombres premiers.

À quelle vitesse se fait le calcul ?

Pour étudier plus précisément le déroulement de l’algorithme et de ses différentes étapes, écrivons de façon plus formelle les instructions contenues dans l’idée de base et attribuons un numéro à chaque étape :

Tableau de nombres premiers_méthode de base
1 Écrire tous les nombres de 2 jusqu’à n dans une liste
2 Pour chaque nombre i := 2…n faire :
3 Pour chaque nombre k := 2…n faire :
4 Supprimer le nombre i . k de la liste

Si lors de l’étape 4 le nombre i . k n’est pas dans la liste, il ne se passe rien.

Cet algorithme peut être programmé très facilement sur un ordinateur et nous pouvons constater le temps nécessaire à son exécution. Sur un PC de 3,2 GHz fonctionnant sous Linux, voici les temps de calcul :

On observe qu’une augmentation de n d’un facteur 10 prolonge le temps de calcul d’un facteur d’environ 100. Ceci est prévisible, car i tout comme k sont pris dans une plage dix fois plus grande. Donc 100 fois plus de produits i . k sont calculés.
De là, nous déduisons que pour arriver à n = 10⁹, nous devons augmenter le temps nécessaire pour n = 10⁶ d’un facteur (10⁹ / 10⁶)² = 10⁶. Nous aurions donc besoin de 1943 . 10⁶ secondes soit 61 ans et 7 mois. C’est naturellement impossible dans la pratique.

Quelles étapes de l’algorithme sont gourmandes en temps ?

L’algorithme génère tous les produits i . k dans une certaine plage :

Toutefois, chaque résultat est utilisé une seule fois. Il est ensuite supprimé de la liste et l’algorithme n’aurait plus jamais besoin de le recalculer. À quel moment travaille-t-il trop ? Notamment là où les valeurs de i et k sont interverties, par exemple i = 3, k = 5 et plus tard i = 5, k = 3. Dans les deux cas, le résultat du produit est le même, car la multiplication est commutative : on obtient toujours i . k = k . i. C’est pourquoi, pour éviter ces doublons, nous pouvons préciser k ≥ i.

Cette idée épargne d’emblée la moitié du travail ! Toutefois, 30 ans et 10 mois restent encore bien trop longs pour obtenir notre tableau. Où pouvons-nous réduire la quantité de travail à réaliser ? Précisément dans l’étape 4 où il ne se passe rien quand i . k > n. La liste contient seulement des nombres jusqu’à n, les nombres au-delà de n ne sont pas pris en compte.
De ce fait, nous avons besoin de la boucle k (ligne 3) seulement pour les valeurs telles que i . k ≤ n. Cette condition même nous donne les valeurs de k : k ≤ n / i.

Nous pouvons simultanément délimiter la plage de valeurs pour i. À partir des deux restrictions i ≤ k ≤ n / i, nous obtenons i² ≤ n, donc i ≤ √n. Pour i supérieur, le domaine k est vide.

Voici comment se présente le nouvel algorithme :

Tableau de nombres premiers_méthode améliorée
1 Ecrire tous les nombres de 2 jusqu’à n dans une suite
2 Pour chaque nombre i := 2… ⌊√n⌋ faire :
3 Pour chaque nombre k := i… ⌊n / i⌋ faire :
4 Supprimer le nombre i . k de la liste

(Le caractère ⌊ ⌋ signifie que le nombre est arrondi puisqu’i et k peuvent seulement prendre des valeurs entières.)
Quelle vitesse atteignons-nous à présent ? Voici les nouveaux temps de calcul :

L’effet bénéfique se fait déjà sentir, l’objectif 10⁹ n’est plus hors d’atteinte : il est seulement à sept minutes et demie. Laissons l’ordinateur travailler et profitons de ce moment pour essayer d’encore améliorer l’algorithme !

Avons-nous besoin de toutes les valeurs de i ?

Observons ce qui se passe exactement dans la boucle i (ligne 2) : i reste le même pendant que k parcourt sa boucle (ligne 3). Ainsi, le produit i . k prend successivement les valeurs
i², i(i+1), i(i+2)…

Au moment où la boucle k est terminée, plus aucun multiple de i ne figure dans la liste. Mais il en va de même pour tous les multiples des nombres inférieurs à i, puisqu’ils ont déjà été supprimés de la même façon.
Que se passe-t-il si i n’est pas un nombre premier ? Prenons par exemple i = 4. Le produit i . k parcourt les valeurs 16, 20, 24… On constate que ces nombres sont tous aussi des multiples de 2, étant donné que 4 est lui-même un multiple de 2. De ce fait, aucun calcul n’est nécessaire pour i = 4. Et il en va de même pour tous les autres nombres pairs i > 4.
Prenons l’exemple i = 9. Le produit i . k parcourt seulement des multiples de 9. En tant que multiples de 3, ils ont déjà été considérés, il est donc inutile de les parcourir à nouveau. Le cas de figure est le même avec tous les nombres qui ne sont pas premiers, car ils ont un diviseur premier plus petit qu’eux, qui représentait avant eux une valeur de i. Nous avons donc besoin de parcourir la boucle k seulement lorsque i est un nombre premier.

Comment savoir si i est un nombre premier ou non ? La liste elle-même pourrait nous l’indiquer – si elle était déjà terminée. C’est seulement après avoir terminé l’exécution de l’algorithme que nous pouvons être certains qu’il reste seulement des nombres premiers dans la liste. Jusqu’ici, vous êtes d’accord ?
Eh bien, oui et non. En général, oui, car sinon nous pourrions abréger l’algorithme. Or cela n’est pas toujours possible. Prenons par exemple n = 100 : le nombre non premier 91 doit être à un moment ou à un autre supprimé de la liste. Il est produit juste avant la fin, il correspond en effet à i = 7, k = 13.
Dans notre cas précis, non, car nous ne cherchons pas à trouver n’importe quel nombre premier, mais à déterminer si un nombre en particulier, le nombre i, est premier. Et ce, pas à n’importe quel moment, mais plutôt au début de la boucle k pour la valeur i. Ici, la liste nous donne une bonne information ! Pourquoi ?
Nous avions observé plus haut que pour chaque valeur de i, toutes les valeurs i . k supprimées sont telles que i . k ≥ i². Autrement dit : dans la suite 2, …, i² – 1, rien n’est modifié. Étant donné que i ne fait qu’augmenter dans le temps, cette suite augmente aussi et comprend toutes les suites formées avant elle. Sur le schéma suivant, ces suites sont représentées en bleu :

Comme plus aucun changement n’apparaît dans ces suites jusqu’à la fin de l’algorithme, elles doivent être déjà correctes avant le passage de la boucle k pour le i que l’on considère. Le tableau est pour ainsi dire prêt en quatre étapes. Ce qui est en vert est la valeur i dont nous souhaitons vérifier la qualité de nombre premier. On constate qu’elle est toujours dans une zone bleue. Pour décider si i est un nombre premier, nous pouvons donc vérifier s’il figure dans la liste courante.
Nous pouvons affiner la boucle i dans l’algorithme comme ci-dessous :

Tableau de nombres premiers_crible d’Ératosthène
1 Ecrire tous les nombres de 2 jusqu’à n dans une liste
2 Pour chaque nombre i :=2… ⌊√n⌋ dans la liste faire :
3 Pour chaque nombre k := i… ⌊n / i⌋ faire :
4 Supprimer le nombre i . k de la liste

C’est ce procédé qui avait été présenté par Ératosthène et qui s’appelle le crible d’Ératosthène d’après son inventeur. C’est un crible, car il ne construit pas méthodiquement les nombres premiers, mais retire au contraire tous les nombres qui ne sont pas premiers.

Voici les temps de calcul pour cet algorithme :

Pour n=10⁹, ça fait encore une bonne minute !

Peut-on faire encore plus rapide ?

Avec un argument similaire à celui pour les valeurs de i, nous pouvons également restreindre les valeurs de la boucle k : nous avons besoin de regarder seulement celles que l’on trouve dans la liste. Si k ne s’y trouve plus, alors k est supprimé en tant que nombre non premier et a un diviseur premier p < k. Au passage de la boucle i avec i = p, tous les multiples de p sont supprimés, en particulier k et ses multiples. Il n’y a donc plus rien à faire à cet endroit.
Il serait logique de compléter l’algorithme comme ci-dessous :

3 Pour chaque nombre k := i… ⌊n / i⌋ dans la liste faire :
4 …

Attention ! Cette formule n’est pas parfaite. Si on exécute l’algorithme de cette manière, il génère le tableau suivant :
2 3 5 7 8 11 12 13 17 19 20 23 27 28 29 31 32 37 41 43 44 …
Qu’est-ce qui ne va pas ? Regardons plus précisément les premières étapes de l’algorithme. Voici le résultat après initialisation de la liste avec tous les nombres jusqu’à n (ligne 1) :
2 3 4 5 6 7 8 9 10 11 …
Tout d’abord, on pose i = 2, puis k = 2. Le nombre 2 est dans la liste, donc on supprime i . k = 4 :
2 3 – 5 6 7 8 9 10 11 …
Ensuite, k = 3. Le nombre 3 est lui aussi dans la liste, donc on supprime i . k = 6 :
2 3 – 5 – 7 8 9 10 11 …
Et maintenant : k = 4 ne figure plus dans la liste, car il a été supprimé en premier. Rien n’est donc fait pour k = 4 à cause de la nouvelle restriction et l’algorithme poursuit avec k = 5 :
2 3 – 5 – 7 8 9 – 11 …

2 . 4 = 8 reste donc par erreur dans la liste. Le problème est que k supprime constamment des nombres plus grands que lui i . k > k lors du passage de la boucle, puis lui-même augmente. À un moment donné, k prend la valeur d’un ancien produit i . k et le procédé a des répercussions néfastes sur lui-même :

La solution est alors de faire passer les valeurs de k par ordre décroissant dans la boucle. Les répercussions néfastes sont ainsi évitées :

Avec ce raisonnement, ne sont formés que les produits suivants i . k :

Il en résulte la version suivante :

Tableau de nombres premiers_crible d’Ératosthène amélioré
1 Ecrire tous les nombres de 2 jusqu’à n dans une liste
2 Pour chaque nombre i := 2… ⌊√n⌋ dans la liste faire :
3 Pour chaque nombre k := ⌊n / i⌋…i dans la liste dans l’ordre décroissant faire :
4 Supprimer le nombre i . k de la liste

Temps de calcul :

Voilà un résultat acceptable pour les standards actuels. Depuis la version de départ sans raisonnement approfondi, nous avons accéléré l’algorithme pour n = 10⁹ d’un facteur de 254,5 millions !

D’autres versions améliorées du crible d’Ératosthène ont été proposées, par exemple le crible d’Atkin en 1999.

Regardez se dérouler en parallèle les différentes variantes de l’algorithme que nous vous avons présentées, pour n = 56. Un temps d’arrêt de 100 ms a été ajouté entre deux calculs consécutifs.

Que nous enseigne cet exemple ?

• Des procédés de calcul simples ne sont pas automatiquement efficaces
• Pour les rendre plus efficaces, nous devons bien comprendre leur fonctionnement
• De nombreuses améliorations sont possibles
• Les idées mathématiques peuvent aller très loin !

Une première version de ce document est parue en allemand dans la série Algorithmus der Woche publiée à l’occasion de l’Année de l’informatique (Informatikjahr) 2006.
Les animations interactives en HTML5/JS ont été réalisées par Ouest INSA, à partir des applets Java de l’article d’origine adaptées par Hamdi Ben Abdallah.