Crible d'Ératosthène et recherche des nombres premiers inférieurs à 100 — 3ème

3ème · Mathématiques 3ème

À retenir

• Le crible d'Ératosthène permet d'obtenir la liste complète des nombres premiers jusqu'à N. • Pour trouver les premiers jusqu'à 100, on raye seulement les multiples des premiers 2, 3, 5, 7 car 11^2 = 121 > 100. • Il y a exactement 25 nombres premiers compris entre 1 et 100.

Le cours

1. Principe algorithmique du crible d'Ératosthène Le crible d'Ératosthène est une méthode historique mise au point par le savant grec Ératosthène de Cyrène (IIIe siècle avant J.-C.) pour extraire efficacement tous les nombres premiers jusqu'à un entier donné N. 1. On écrit tous les entiers de 2 jusqu'à N dans une grille (le nombre 1 est rayé d'office car il n'est pas premier). 2. On entoure le premier nombre non rayé (c'est 2), puis on raye tous ses multiples stricts (4, 6, 8, 10 ). 3. On entoure le prochain nombre non rayé (3) et on raye tous ses multiples stricts (6, 9, 12, 15 ). 4. On réitère le processus avec les nombres suivants non rayés. 2. Condition d'arrêt du crible Pour trouver tous les nombres premiers inférieurs ou égaux à 100, il est inutile de tester tous les entiers jusqu'à 100 : On s'arrête dès que le carré du nombre premier dépasse la borne maximale N : p^2 > N. Comme 7^2 = 49 100 et que le nombre premier suivant est 11 avec 11^2 = 121 > 100, il suffit de rayer les multiples des nombres premiers 2, 3, 5 et 7 ! Tous les entiers non rayés restants entre 2 et 100 sont alors obligatoirement des nombres premiers. 3. Erreurs classiques Attention à ne pas considérer 1 comme un nombre premier : un nombre premier possède par définition exactement deux diviseurs distincts (1 et lui-même), or 1 n'en a qu'un seul. De même, 91 semble souvent premier au premier coup d'œil, mais 91 = 7 13, il n'est donc pas premier.

Dans ce chapitre