Crible d'Ératosthène

Infos
Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est l'ancêtre du plus récent crible d'Atkin qui est plus rapide mais plus complexe.
Crible d'Ératosthène

Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est l'ancêtre du plus récent crible d'Atkin qui est plus rapide mais plus complexe.

Algorithme

On forme une table avec tous les entiers naturels compris entre 2 et N et on raye les uns après les autres, les entiers qui ne sont pas premiers de la manière suivante : dès que l'on trouve un entier qui n'a pas encore été rayé, il est déclaré premier, et on raye tous les autres multiples de celui-ci. Étudions un exemple pour les entiers inférieurs à 120 : center Déterminons pas à pas la liste de tous les nombres premiers inférieurs à 20 : Étape 1. Écrivons la liste des nombres naturels compris entre 2 et 20 Étape 2. On marque le nombre suivant non rayé de la liste, comme premier. Étape 3. On raye dans la liste, tous les multiples du nombre que l'on vient d'entourer. Étape 4. Si le carré du nombre suivant non rayé est inférieur à 20, alors on recommence à l'étape 2 sinon on déclare tous les entiers restants non rayés premiers. Puisque 3 élevé au carré est inférieur à 20, on retourne à l'étape 2 : À l'étape 4, l'entier suivant non rayé 5 a un carré strictement supérieur à 20, on considère comme premiers tous les entiers suivants non rayés. Résultat : Les entiers premiers compris entre 2 et 20 sont : 2, 3, 5, 7, 11, 13, 17, 19. Pour obtenir les entiers premiers inférieurs à N=99, on raye dans l'ordre tous les multiples des nombres premiers p=2, 3, 5, 7, … à partir de p^2 jusqu'à N. On s'arrête lorsque l'entier premier p suivant vérifie p^2>N (Si un entier non premier est strictement supérieur à \sqrt alors il a au moins un diviseur inférieur à \sqrt et aura donc déjà été rayé). On va donc aller jusqu'à p=9, parce que 102=100>99, et déclarer premiers tous les entiers non rayés suivants. On obtient la table suivante :

Le crible d'Eratosthène codé en C

Voici ce que donne le crible d'Eratosthène codé en C (seule la fonction qui permet de calculer les nombres premiers est affichée ici)
- Remarque : le tableau "tableau" de nombres entiers (entre 2 et N) doit être créé et rempli avant l'utilisation de cette fonction 1 void premiers(long tableau, long tailleTableau) 2 3 int i = 0, y = 0; 4 long diviseur = 0; 5 6 7 for (i = 0 ; i < sqrt(tailleTableau) ; i++) 8 19 20 21 for (i = 0 ; i < tailleTableau ; i++) 22 if (tableau != 0) 23 printf ("%ld ", tableau); 24
- Lignes 3 à 4 : Déclaration des variables nécessaires ("i" et "y" pour parcourir le tableau "tableau" et "diviseur" pour tester si un nombre est premier ou pas).
- Ligne 9 : On vérifie si on a pas déjà supprimé le nombre, si ce n'est pas le cas on continue, sinon, on passe au nombre suivant.
- Ligne 11 : On associe à la variable "diviseur" la valeur du nombre présent à l'emplacement "y" du tableau "tableau".
- Lignes 13 à 16 : On regarde si les nombres qui suivent l'emplacement initial d'"y" divisés par "diviseur" forment un reste nul ou pas. S'ils forment un reste nul, ils ne sont pas premiers, on les raye.
- Lignes 21 à 23 : Si le nombre situé à l'emplacement "y" du tableau "tableau" n'est pas rayé (égal à zéro), on l'affiche.

Notes et Références

Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347. ==
Sujets connexes
Crible d'Atkin   Entier naturel   Nombre premier  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^