Crible d'Erathostène.

Le crible d'Erathostène, un contemporain d'Achimède, permet de déterminer tous les nombres premiers inférieurs à un nombre entier N.

Rappel: un nombre naturel est dit premier si aucun nombre ne le divise sauf 1 et lui-même. Par convention, 1 n'est pas considéré comme premier.

A titre indicatif, le plus grand nombre premier connu est 21257787-1. Ce nombre s'écrit avec 378632 chiffres.

Voici les différentes étapes de l'algorithme:

Placer d'abord les nombres 1, 2, 3, ..., N dans un tableau.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Commencer avec l'élément en 2ème position et continuer avec les suivants:
si l'élément en position i a été supprimé, passer au suivant
sinon, supprimer tous les éléments du tableau (mais pas lui) dont le numéro de position est un multiple de i
Ceci donne:
i=2 : l'élément en 2ème position vaut 2. Supprimons donc les éléments en positions 4, 6, ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 2 3 x 5 x 7 x 8 x 9 x 11 x 13 x 15 x 19

i=3 : l'élément en 3ème position vaut 3. Supprimons donc les éléments en positions 6, 9, 12, ...
Note: l'élément en position 6 a été supprimé pour la 2ème fois mais ceci ne pose aucun problème.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 2 3 x 5 x 7 x 9 x 11 x 13 x x x 17 x 19

i=4 : l'élément en 4ème position a été supprimé. Ne rien faire.
Comme on peut le constater, seuls subsistent les nombres premiers.
Informatiquement, se pose le problème de la suppression des multiples de 2, 3, ... Le plus simple, comme on se trouve dans un tableau de nombre, est de remplacer le nombre supprimé par 0.
Il est également évident que dans le tableau, il est inutile de stocker un nombre (puisqu'il est égal à sa position); un booléen fera tout aussi bien l'affaire.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
V V V F V F V F V F V F V F F F V F V



Il faut noter que Erathostène positionnait les nombres comme ci-dessous et supprimait les verticales et obliques correspondant aux différents multiples:
en rouge, les verticales "multiples" de 2
en bleu, les obliques "multiples" de 3
en blanc, la verticale "multiple" de 5
en jaune, les obliques "multiples" de 7

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100 


PROGRAM Erathostene;

CONST N=1000;

VAR A:ARRAY[1..N] OF BOOLEAN;
    i,j,M:WORD;

BEGIN
FOR i:=1 TO N DO A[i]:=TRUE;
M:=TRUNC(SQRT(N));
FOR i:=2 TO M DO
  IF A[i] THEN FOR j:=2 TO N DIV i DO A[i*j]:=FALSE;
FOR i:=1 TO N DO IF A[i] THEN WRITE(i:5);
END.
Page précédente.
Page d'accueil.