Défi final

Dans ce défi, notre but est d'implémenter le Crible d'Ératosthène. Cet algorithme imaginé par Ératosthène (un savant grec antique) permet de trouver tous les nombres premiers inférieurs à un certain nombre. Un nombre premier est un nombre qui n'est divisible que par 1 et lui-même, comme 5, 7 ou 31. Nous allons implémenter pas à pas son algorithme :

1
limite = ?
2
L = liste des entiers de 2 à limite
3
primeNumbers = []
4
5
Tant que L est non vide faire:
6
  Ajouter L[0] à nbPremiers
7
  i prend la valeur 1
8
  Tant que i < longueur(L) faire:
9
    Si L[i] est multiple de L[0]:
10
      Enlever L[i] de L
11
    Sinon:
12
      Incrémenter i
13
    FinSi
14
  FinTantQue
15
  Retirer le premier élément de L
16
FinTantQue
17
18
Afficher nbPremiers
Cet algorithme consiste à regarder, pour chaque entier à une position donnée, s'il est multiple d'un entier qui le précède. Si oui, il est éliminé de la liste car il n'est pas premier.
Voici le squelette que nous allons compléter petit à petit :
1
const limit = Number(prompt('Entrer la limite du crible'))
2
3
// Liste des premiers nombres entiers jusqu'à limit
4
const L = []
5
for (let i = 2; i <= limit; i++) {
6
  L.push(i)
7
}
8
const primeNumbers = []
9
10
while (/* A Compléter */) {
11
  // A compléter
12
}
13
14
console.log(primeNumbers)
Question
Quelle sera la condition du while ?
Indice
Comment vérifier si L est vide ou non ? Quelle est la longueur d'une liste vide ?
Solution
1
L.length > 0
On aurait aussi pu écrire :
1
L.length != 0
Question
Traduire les premières lignes du while, rappelées ci-dessous. Pour ajouter un élément à une liste, il faut faire liste.push(element).
1
  Ajouter L[0] à primeNumbers
2
  i prend la valeur 1
Solution
1
  primeNumbers.push(L[0])
2
  i = 1
Question
Voici le squelette de la boucle imbriquée, complétez-le :
1
  while(?) {
2
    if (?) {
3
      ?
4
    } else {
5
      ?
6
    }
7
  }
Indice
Pour retirer le i-ème élément d'une liste il faut écrire liste.splice(i, 1).
Indice
Pour incrémenter une variable entier, il faut écrire entier++.
Indice
Pour vérifier si b est multiple de a, il est possible d'écrire la condition suivante : a % b === 0.
Solution
1
  while(i < L.length) {
2
    if (L[i] % L[0] === 0) {
3
      L.splice(i, 1)
4
    } else {
5
      i++
6
    }
7
  }
Question
Donner le programme complet :
Solution
1
const limit = Number(prompt('Entrer la limite du crible'))
2
const L = []
3
for (let i = 2; i <= limit; i++) {
4
  L.push(i)
5
}
6
const primeNumbers = []
7
8
while (L.length > 0) {
9
  primeNumbers.push(L[0])
10
  let i = 1
11
  while (i < L.length) {
12
    if (L[i] % L[0] === 0) {
13
      L.splice(i, 1)
14
    } else {
15
      i++
16
    }
17
  }
18
  L.splice(0, 1)
19
}
20
21
console.log(primeNumbers)
22
Question
Quel est le résultat de l'algorithme pour n = 50 ?
Solution
1
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
2