Le crible d'Eratosthènes : L'algorithme est utilisé pour trouver (identifier) les nombres premiers dans une liste. Astuce : commencez par barrer les multiples des plus petits nombres premiers

Le mathématicien grec Ératosthène de Cyrène (276 - 194 av. J.-C.) a utilisé une méthode nouvelle et simple pour déterminer si les nombres d'une liste sont premiers ou non.
Il a commencé par les petits nombres premiers bien connus 2, 3, 5, 7, 11, 13, 17, 23, etc. Il est clair que tous leurs multiples ne sont pas des nombres premiers mais des nombres composés.
Il a organisé une liste de nombres naturels par ordre croissant. Ensuite, il a identifié et supprimé tous les nombres composés les plus grands de cette liste car ils sont des multiples des premiers nombres premiers. De cette façon, il a séparé les plus grands nombres premiers de cette liste.
Nous illustrons cette méthode ci-dessous, avec une liste de nombres triés par ordre croissant, de 2 à 100 :

Le nombre 2 est un nombre premier, donc on identifie d'abord tous les multiples de 2 dans la liste :
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'au nombre : 2 × 50 = 100.
Le nombre 2 × 51 = 102, est supérieur à 100, nous pouvons donc nous arrêter.
Supprimez tous les multiples du nombre 2 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.

Le nombre 3 est un nombre premier, donc on identifie d'abord tous les multiples de 3 dans la liste :
3 × 2 = 6 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
3 × 3 = 9
3 × 4 = 12 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
3 × 5 = 15
3 × 6 = 18 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
... et ainsi de suite, jusqu'au nombre: 3 × 33 = 99.
The number 3 × 34 = 102, est supérieur à 100, nous pouvons donc nous arrêter.
Supprimez tous les multiples du nombre 3 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.
Si nous avons déjà supprimé tous les multiples du nombre 2 de la liste, il ne nous reste plus que : 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93. 99. Ces nombres sont écrits ci-dessous, comme des multiples du nombre 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.

On procède alors avec le nombre premier suivant, 5 :
5 × 2 = 10 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
5 × 3 = 15 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 3);
5 × 4 = 20 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
5 × 5 = 25
5 × 6 = 30 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2 et 3);
5 × 7 = 35
... et ainsi de suite, jusqu'au nombre: 5 × 20 = 100 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2).
The number 5 × 21 = 105, est supérieur à 100, nous pouvons donc nous arrêter.
Supprimez tous les multiples du nombre 5 de la liste : 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100.
Si nous ne nous occupons pas des multiples de 2 et 3, qui ont déjà été supprimés de la liste, il nous reste encore ces nombres à supprimer : 25, 35, 55, 65, 85, 95, c'est-à-dire. exactement les nombres qui n'ont dans leur décomposition en facteurs premiers que des facteurs 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 répétons le processus avec le prochain nombre premier, 7 :
7 × 2 = 14 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
7 × 3 = 21 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 3);
7 × 4 = 28 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2);
7 × 5 = 35 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 5);
7 × 6 = 42 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2 et 3);
7 × 7 = 49
... et ainsi de suite, jusqu'au nombre: 7 × 14 = 98 (Ce nombre a déjà été supprimé de la liste, il est un multiple de 2).
7 × 15 = 105, est supérieur à 100, nous pouvons donc nous arrêter.
Supprimez tous les multiples du nombre 7 de la liste : 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.
Si nous ne nous occupons pas des multiples de 2, 3 et 5, qui ont déjà été supprimés de la liste, nous devons encore supprimer : 49, 77, 91. Ce sont précisément les nombres qui ont dans leur décomposition des facteurs premiers supérieurs ou égaux à 7 :
7 × 7 = 49
7 × 11 = 77
7 × 13 = 91.

Le nombre premier suivant dans la liste est 11 et nous devrions supprimer les multiples de 11 de la liste.
Cependant, comme nous l'avons vu dans les étapes ci-dessus, nous devrions essayer de supprimer de la liste uniquement les nombres ayant dans leur décomposition des facteurs premiers supérieurs ou égaux à 11.
Mais 11 × 11 = 121, qui est supérieur à 100.
Cela signifie que tous les nombres qui sont restés dans la liste après avoir effectué les étapes ci-dessus sont déjà des nombres premiers.

La liste des nombres premiers est constituée des nombres non supprimés.
Après avoir retiré de la liste tous les multiples des nombres premiers 2, 3, 5 et 7, nous avons encore dans la liste les nombres suivants : 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 - la liste des nombres premiers de 2 à 100.

fr.numere-prime.ro