Le crible d'Eratosthènes: l'algorithme pour trouver les nombres premiers dans une liste; retirer les multiples des nombres premiers plus petits

Le mathématicien grec ERATOSTENE (275 - 194 av. J.-C.) a appliqué une nouvelle méthode simple pour déterminer si les nombres d'une liste sont premiers ou non. A partir des petits nombres premiers connus, 2, 3, 5, 7, 11, 13, 17, 21, etc., il est clair que tous leurs multiples ne sont pas des nombres premiers mais composés. Il a ordonné une liste de nombres naturels dans l'ordre croissant et ensuite il a enlevé tous les multiples des premiers nombres premiers pour identifier le reste des plus grands nombres premiers dans cette liste. Nous allons illustrer cette méthode ci-dessous sur une liste de nombres allant de 2 à 100:

  • Le nombre 2 est premier, donc nous enlevons de cette chaîne tous les multiples de 2: 2 × 2 = 4; 2 × 3 = 6; 2 × 4 = 8; 2 × 5 = 10; 2 × 6 = 12; 2 × 7 = 14; 2 × 8 = 16; 2 × 9 = 18; 2 × 10 = 20; ... et ainsi de suite jusqu'à 2 × 50 = 100. 2 × 51 = 102, est supérieur à 100, donc nous nous arrêtons.
  • Multiples de 2 à retirer de la liste: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100 (numéros deux par deux).
  • 3 est le nombre premier suivant, donc nous allons supprimer de la liste tous les multiples de 3: 3 × 2 = 6 (qui a déjà été retiré de la liste, étant un multiple de 2); 3 × 3 = 9; 3 × 4 = 12 (qui a déjà été retiré de la liste, étant un multiple de 2); 3 × 5 = 15; 3 × 6 = 18 (qui a déjà été retiré de la liste, étant un multiple de 2); ... et ainsi de suite jusqu'à: 3 × 33 = 99. 3 × 34 = 102, est supérieur à 100 donc nous nous arrêtons.
  • Multiples de 3 à retirer de la liste: 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 97, 99 (numéros trois par trois). Si nous ne regardons pas les multiples de 2 qui ont déjà été supprimés de la liste, nous avons toujours: 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, c'est-à-dire. les nombres qui n'ont comme facteurs que les nombres premiers supérieurs ou égaux à 3: 3 × 3 = 9; 3 × 5 = 15; 3 × 7 = 21; 3 × 9 = 3 × 3 × 3 = 27; 3 × 11 = 33; 3 × 13 = 39; 3 × 15 = 3 × 3 × 5 = 45; 3 × 17 = 51; 3 × 19 = 57; 3 × 21 = 3 × 3 × 7 = 63; 3 × 23 = 69; 3 × 25 = 3 × 5 × 5 = 75; 3 × 27 = 3 × 3 × 3 × 3 = 81; 3 × 29 = 87; 3 × 31 = 93; 3 × 33 = 3 × 3 × 11 = 99.
  • Nous allons également procéder avec le nombre premier suivant, 5: 5 × 2 = 10 (qui a déjà été retiré de la liste, étant un multiple de 2); 5 × 3 = 15 (qui a déjà été retiré de la liste, étant un multiple de 3); 5 × 4 = 20 (qui a déjà été retiré de la liste, étant un multiple de 2); 5 x 5 = 25; 5 × 6 = 30 (qui a déjà été retiré de la liste, étant à la fois un multiple de 2 et 3); 5 × 7 = 35; ... et ainsi de suite jusqu'à: 5 × 20 = 100 (qui a déjà été retiré de la liste, étant un multiple de 2). 5 × 21 = 105, est supérieur à 100, donc nous nous arrêtons.
  • Multiples de 5 à retirer de la liste: 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (cinq par cinq numéros). Si nous ne regardons pas les multiples de 2 et 3, qui ont déjà été supprimés de la liste, nous devons toujours supprimer: 25, 35, 55, 65, 85, 95, exactement les nombres qui n'ont comme facteurs que les nombres premiers supérieurs ou égaux à 5: 5 × 5 = 25; 5 × 7 = 35; 5 × 11 = 55; 5 × 13 = 65; 5 × 17 = 85; 5 × 19 = 95.
  • Ensuite, nous faisons la même chose avec le nombre premier suivant, 7: 7 × 2 = 14 (qui a déjà été retiré de la liste, étant un multiple de 2); 7 × 3 = 21 (qui a déjà été retiré de la liste, étant un multiple de 3); 7 × 4 = 28 (qui a déjà été retiré de la liste, étant un multiple de 2); 7 × 5 = 35 (qui a déjà été retiré de la liste, étant un multiple de 5); 7 × 6 = 42 (qui a déjà été retiré de la liste, étant à la fois un multiple de 2 et 3); ... 7 × 7 = 49; ... et ainsi de suite jusqu'à: 7 × 14 = 98 (qui a déjà été retiré de la liste, étant un multiple de 2). 7 × 15 = 105, est supérieur à 100, donc nous nous arrêtons.
  • Multiples de 7 à retirer de la liste: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98 (sept-par-sept nombres). Si nous ne regardons pas les multiples de 2, 3 et 5, qui ont déjà été supprimés de la liste, nous devons toujours supprimer: 49, 77, 91, exactement les nombres qui ont comme diviseurs seulement des nombres premiers supérieurs ou égaux à 7: 7 × 7 = 49; 7 × 11 = 77; 7 × 13 = 91.
  • Le prochain nombre premier dans la liste est 11 et nous devrions enlever de la liste les multiples de 11; Cependant, comme nous l'avons vu ci-dessus, nous ne devrions retirer de la liste que les nombres premiers ayant des nombres premiers supérieurs ou égaux à 11. Mais déjà 11 × 11 = 121 est supérieur à 100, cela signifie que tous les nombres restant dans la liste après le processus décrit ci-dessus sont déjà des nombres premiers.
  • Après avoir supprimé de la liste tous les multiples des nombres premiers: 2, 3, 5 et 7, nous avons toujours dans la liste: 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, c'est-à-dire, la liste des nombres premiers de 2 à 100.

Qu'est-ce qu'un nombre premier?

Qu'est-ce qu'un nombre composé?

Nombres premiers jusqu'à 1.000

Nombres premiers jusqu'à 10.000

La crible d'Ératosthène

Algorithme d' Euclide

Simplifier des fractions mathématiques ordinaires: mesures et des exemples