retour au cours

Extraire des nombres premiers

importance: 3

Un nombre entier supérieur à 1 est appelé un Nombre premier s’il ne peut être divisé sans reste par rien d’autre que 1 et lui-même.

En d’autres termes, n > 1 est un nombre premier s’il ne peut être divisé de manière égale par autre chose que 1 et n.

Par exemple, 5 est un nombre premier, car il ne peut pas être divisé sans reste par 2, 3 et 4.

Écrivez un code qui produit les nombres premiers dans l’intervall e 2 à n.

Pour n = 10, le résultat sera 2,3,5,7.

P.S. Le code devrait fonctionner pour n’importe quel n et aucune valeur fixe ne doit être codé en dur.

Il existe de nombreux algorithmes pour cette tâche.

Utilisons une boucle imbriquée :

Pour chaque i dans l'intervalle {
  vérifier si i a un diviseur de 1..i
  si oui => la valeur n'est pas un nombre premier
  si non => la valeur est un nombre premier, affichez-le
}

Un code utilisant un label :

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // Pour chaque i...

  for (let j = 2; j < i; j++) { // cherche un diviseur ..
    if (i % j == 0) continue nextPrime; // pas un premier, on passe au prochain i
  }

  alert( i ); // un premier
}

Il y a beaucoup d’espace pour l’optimiser. Par exemple, nous pourrions rechercher les diviseurs de 2 à la racine carrée de i. Quoi qu’il en soit, si nous voulons être vraiment efficaces pour les grands intervalles, nous devons changer d’approche et nous baser sur des mathématiques avancées et des algorithmes complexes comme Crible quadratique, Crible algébrique etc.