L’algorithme du sieve of Eratosthenes

Fraser Mummery

Eratosthenes of Cyrene est un mathématicien, géographe, poète, astronome et théoricien de la musique né en Grèce antique. Il a été un grand penseur, à l’origine notamment des premières cartes représentatives du monde, tel que celui-ci était connu à l’époque. C’est à lui que l’on doit entre autres, le jour bissextile (le 29 février), de nombreuses découvertes en matière de géographie dont une approximation raisonnable du diamètre de la Terre, et le fameux crible d’Ératosthène.

Cet algorithme est une manière efficace de retrouver tous les nombres premiers. Celui-ci consiste à tester la primalité des nombres de 2 à n selon la méthode décrite ci-après.

L’algorithme du crible d’Ératosthène décrypté

Considérons une liste de nombres entiers de 2 à n, 2 étant le premier des nombres premiers. On récupère tous les multiples de 2 appartenant à cette liste, et on les marque comme étant non premiers : par définition, tout multiple de 2 est divisible par 2. Le multiple d’un nombre ne peut donc pas être premier.

On cherche ensuite le premier des nombres supérieurs à 2 n’étant pas marqué dans la liste, et on répète la précédente instruction, à savoir marquer comme étant non premiers tous les multiples de ce nombre. On récupère ainsi le nombre 3 et on parcourt ses multiples afin de les marquer comme nombre non premier.

Chacune de ces opérations est répétée jusqu’à ce que l’on arrive à la limite de cette liste, le nombre n. Quand l’algorithme se termine, tous les nombres qui n’auront pas été marqués dans la liste constituent la séquence de nombres premiers inférieurs à n.

Animation of the Sieve of Eratosthenes

Chacun des nombres restants une fois l’algorithme terminé est nécessairement nombre premier, car tous les multiples des nombres inférieurs auront déjà été marqués. Il se peut, par ailleurs, qu’un multiple ait déjà été marqué : c’est le cas du nombre 6 par exemple. Ce nombre est marqué originellement comme étant non premier car il est multiple de 2. 6 étant également multiple de 3, il pourrait éventuellement être marqué une deuxième fois.

Une évolution de l’algorithme énoncé ci-dessus serait de commencer à marquer tous les multiples d’un nombre premier à partir du carré de celui-ci, car tous les plus petits multiples de celui-ci auront d’ores-et-déjà été marqués. Cela signifie aussi que l’algorithme peut se terminer lorsque le carré d’un des nombres premiers trouvés est supérieurs à n.

…en JavaScript

Ci-dessous, une des écritures possibles de cet algorithme en JavaScript, permettant d’obtenir tous les nombres premiers inférieurs à n. detectprimes est un tableau de n booléens. On attribue la valeur true à l’ensemble des nombres de 2 à n, 0 et 1 ne faisant pas partie de cet ensemble sont initialisés avec la valeur false.

Une boucle for est mise en place, avec une limite de √n. À chaque nouvelle itération sur le tableau de n nombres, on vérifie si p est premier – si p est égal à true – et seulement à cette condition, on évalue tous les multiples de p supérieurs au carré de p, afin de les marquer à false, comme étant non premiers donc.

Il ne reste ensuite qu’à parcourir les éléments du tableau detectprimes, afin de récupérer tous les nombres premiers inférieurs à n.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();

  // Set detectprimes with boolean values
  detectprimes[0] = false;
  detectprimes[1] = false;
  for(var i = 2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  // Mark all multiples as false
  for(var p = 2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      for(var j = p*p; j < n; j += p)
        detectprimes[j] = false;
    }
  }

  // Get all the prime numbers
  for (var i = 0; i < n; i++)
    if(detectprimes[i]) primes.push(i);
  return primes;
}

Pour vérifier le bon comportement de la fonction que je vous propose, voici une représentation textuelle de l'image qui schématise l'algorithme proposé par Ératosthène.

En exécutant le code présent ci-après, vous pourrez mieux appréhender le déroulement du crible d'Ératosthène. Cette nouvelle version, proposant des commentaires, à l'aide de console.log est bien évidemment moins efficace en terme de performance, mais vous permettra de suivre chacun des tests effectués à chacune des itérations de la boucle.

function eratosthenes(n) {
  var detectprimes = new Array(n),
      primes = new Array();
  console.log('I want to know which numbers below ' + n + ' are primes.');

  // Set detectprimes with boolean values
  detectprimes[0] = false;
  detectprimes[1] = false;
  for(var i = 2; i < detectprimes.length; i++)
    detectprimes[i] = true;

  // Mark all multiples as false
  for(var p = 2; p < Math.sqrt(n); p++) {
    if(detectprimes[p]) {
      console.log(p + ' is a prime, let\'s mark all its multiples below ' + n + '.');
      for(var j = p*p; j < n; j += p){
        console.log(j + ' is a multiple of '+p+', so ' + j + ' is not a prime.');
        detectprimes[j] = false;
      }
    }else{
      console.log(p + ' is not a prime, so the loop continues.');     
    }
  }
  console.log(p + ' is not smaller than ' + Math.sqrt(n) + ': end of the loop.');

  // Get all the prime numbers
  var _text = 'The primes below ' + n + ' are: ';
  for (var k = 0; k < n; k++) {
    if (detectprimes[k]) {
      primes.push(k);
      if (primes.length == 1) _text += k;
      else _text += ', ' + k;
    }
  }
  console.info(_text + '.');
  return primes;
}
eratosthenes(121);

Vous aurez dans votre console la sortie suivante :

I want to know which numbers below 121 are primes.

2 is a prime, let’s mark all its multiples below 121.
4 is a multiple of 2, so 4 is not a prime.
6 is a multiple of 2, so 6 is not a prime.
8 is a multiple of 2, so 8 is not a prime.
10 is a multiple of 2, so 10 is not a prime.
12 is a multiple of 2, so 12 is not a prime.
14 is a multiple of 2, so 14 is not a prime.
16 is a multiple of 2, so 16 is not a prime.
18 is a multiple of 2, so 18 is not a prime.
20 is a multiple of 2, so 20 is not a prime.
22 is a multiple of 2, so 22 is not a prime.
24 is a multiple of 2, so 24 is not a prime.
26 is a multiple of 2, so 26 is not a prime.
28 is a multiple of 2, so 28 is not a prime.
30 is a multiple of 2, so 30 is not a prime.
32 is a multiple of 2, so 32 is not a prime.
34 is a multiple of 2, so 34 is not a prime.
36 is a multiple of 2, so 36 is not a prime.
38 is a multiple of 2, so 38 is not a prime.
40 is a multiple of 2, so 40 is not a prime.
42 is a multiple of 2, so 42 is not a prime.
44 is a multiple of 2, so 44 is not a prime.
46 is a multiple of 2, so 46 is not a prime.
48 is a multiple of 2, so 48 is not a prime.
50 is a multiple of 2, so 50 is not a prime.
52 is a multiple of 2, so 52 is not a prime.
54 is a multiple of 2, so 54 is not a prime.
56 is a multiple of 2, so 56 is not a prime.
58 is a multiple of 2, so 58 is not a prime.
60 is a multiple of 2, so 60 is not a prime.
62 is a multiple of 2, so 62 is not a prime.
64 is a multiple of 2, so 64 is not a prime.
66 is a multiple of 2, so 66 is not a prime.
68 is a multiple of 2, so 68 is not a prime.
70 is a multiple of 2, so 70 is not a prime.
72 is a multiple of 2, so 72 is not a prime.
74 is a multiple of 2, so 74 is not a prime.
76 is a multiple of 2, so 76 is not a prime.
78 is a multiple of 2, so 78 is not a prime.
80 is a multiple of 2, so 80 is not a prime.
82 is a multiple of 2, so 82 is not a prime.
84 is a multiple of 2, so 84 is not a prime.
86 is a multiple of 2, so 86 is not a prime.
88 is a multiple of 2, so 88 is not a prime.
90 is a multiple of 2, so 90 is not a prime.
92 is a multiple of 2, so 92 is not a prime.
94 is a multiple of 2, so 94 is not a prime.
96 is a multiple of 2, so 96 is not a prime.
98 is a multiple of 2, so 98 is not a prime.
100 is a multiple of 2, so 100 is not a prime.
102 is a multiple of 2, so 102 is not a prime.
104 is a multiple of 2, so 104 is not a prime.
106 is a multiple of 2, so 106 is not a prime.
108 is a multiple of 2, so 108 is not a prime.
110 is a multiple of 2, so 110 is not a prime.
112 is a multiple of 2, so 112 is not a prime.
114 is a multiple of 2, so 114 is not a prime.
116 is a multiple of 2, so 116 is not a prime.
118 is a multiple of 2, so 118 is not a prime.
120 is a multiple of 2, so 120 is not a prime.

3 is a prime, let’s mark all its multiples below 121.
9 is a multiple of 3, so 9 is not a prime.
12 is a multiple of 3, so 12 is not a prime.
15 is a multiple of 3, so 15 is not a prime.
18 is a multiple of 3, so 18 is not a prime.
21 is a multiple of 3, so 21 is not a prime.
24 is a multiple of 3, so 24 is not a prime.
27 is a multiple of 3, so 27 is not a prime.
30 is a multiple of 3, so 30 is not a prime.
33 is a multiple of 3, so 33 is not a prime.
36 is a multiple of 3, so 36 is not a prime.
39 is a multiple of 3, so 39 is not a prime.
42 is a multiple of 3, so 42 is not a prime.
45 is a multiple of 3, so 45 is not a prime.
48 is a multiple of 3, so 48 is not a prime.
51 is a multiple of 3, so 51 is not a prime.
54 is a multiple of 3, so 54 is not a prime.
57 is a multiple of 3, so 57 is not a prime.
60 is a multiple of 3, so 60 is not a prime.
63 is a multiple of 3, so 63 is not a prime.
66 is a multiple of 3, so 66 is not a prime.
69 is a multiple of 3, so 69 is not a prime.
72 is a multiple of 3, so 72 is not a prime.
75 is a multiple of 3, so 75 is not a prime.
78 is a multiple of 3, so 78 is not a prime.
81 is a multiple of 3, so 81 is not a prime.
84 is a multiple of 3, so 84 is not a prime.
87 is a multiple of 3, so 87 is not a prime.
90 is a multiple of 3, so 90 is not a prime.
93 is a multiple of 3, so 93 is not a prime.
96 is a multiple of 3, so 96 is not a prime.
99 is a multiple of 3, so 99 is not a prime.
102 is a multiple of 3, so 102 is not a prime.
105 is a multiple of 3, so 105 is not a prime.
108 is a multiple of 3, so 108 is not a prime.
111 is a multiple of 3, so 111 is not a prime.
114 is a multiple of 3, so 114 is not a prime.
117 is a multiple of 3, so 117 is not a prime.
120 is a multiple of 3, so 120 is not a prime.

4 is not a prime, so the loop continues.

5 is a prime, let’s mark all its multiples below 121
25 is a multiple of 5, so 25 is not a prime.
30 is a multiple of 5, so 30 is not a prime.
35 is a multiple of 5, so 35 is not a prime.
40 is a multiple of 5, so 40 is not a prime.
45 is a multiple of 5, so 45 is not a prime.
50 is a multiple of 5, so 50 is not a prime.
55 is a multiple of 5, so 55 is not a prime.
60 is a multiple of 5, so 60 is not a prime.
65 is a multiple of 5, so 65 is not a prime.
70 is a multiple of 5, so 70 is not a prime.
75 is a multiple of 5, so 75 is not a prime.
80 is a multiple of 5, so 80 is not a prime.
85 is a multiple of 5, so 85 is not a prime.

90 is a multiple of 5, so 90 is not a prime.
95 is a multiple of 5, so 95 is not a prime.
100 is a multiple of 5, so 100 is not a prime.
105 is a multiple of 5, so 105 is not a prime.
110 is a multiple of 5, so 110 is not a prime.
115 is a multiple of 5, so 115 is not a prime.
120 is a multiple of 5, so 120 is not a prime.

6 is not a prime, so the loop continues.

7 is a prime, let’s mark all its multiples below 121.
49 is a multiple of 7, so 49 is not a prime.
56 is a multiple of 7, so 56 is not a prime.
63 is a multiple of 7, so 63 is not a prime.
70 is a multiple of 7, so 70 is not a prime.
77 is a multiple of 7, so 77 is not a prime.
84 is a multiple of 7, so 84 is not a prime.
91 is a multiple of 7, so 91 is not a prime.
98 is a multiple of 7, so 98 is not a prime.
105 is a multiple of 7, so 105 is not a prime.
112 is a multiple of 7, so 112 is not a prime.
119 is a multiple of 7, so 119 is not a prime.

8 is not a prime, so the loop continues.

9 is not a prime, so the loop continues.

10 is not a prime, so the loop continues.

11 is not smaller than 11, end of the loop.

The primes below 121 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113.

Pour aller plus loin : bien d'autres algorithmes proposent de récupérer l'ensemble des nombres premiers, d'autres mêmes jugés encore plus rapides d'exécution que le crible d'Ératosthène comme le sieve of Atkins ou encore le sieve of Sundaram, pour ne citer qu'eux.

Mais le sieve of Eratosthenes que je vous propose aujourd'hui est l'un des plus simples à écrire, et il a la particularité de dater du IIIème siècle avant Jésus-Christ, une prouesse mathématique pour l'époque !