Crible d'Ératosthène

Un article de Wikipédia, l'encyclopédie libre.

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.

[modifier] 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 :

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² jusqu'à N. On s'arrête lorsque l'entier premier p suivant vérifie p² > N (Si un entier non premier est strictement supérieur à alors il a au moins un diviseur inférieur à et aura donc déjà été rayé). On va donc aller jusqu'à p=9, parce que 10²=100>99, et déclarer premiers tous les entiers non rayés suivants. On obtient la table suivante :

[modifier] Le crible d'Eratosthène en Python

Le crible d'Eratosthène s'implémente facilement en Python avec une fonction récursive, qu'il suffit ensuite d'appeler avec en argument le tableau initial (qui doit commencer par 2) :

def crible(tableau):
        if not tableau or tableau[0]**2 > tableau[-1]: return tableau
        return tableau[:1] + crible([i for i in tableau if i%tableau[0]])
 
print crible(range(2,1000))

Comme souvent avec les fonctions récursives, le code obtenu est concis mais peu efficace pour de grandes valeurs de N.

[modifier] 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      {
9              if (tableau[i] != 0)
10             {
11             diviseur = tableau[i];
12                     
13                     for (y = (i+1) ; y < tailleTableau ; y ++)
14                                if ((tableau[y]%diviseur) == 0)
15                                     tableau[y] = 0;
16             
17             }
18     }
19
20
21     for (i = 0 ; i < tailleTableau ; i++)
22             if (tableau[i] != 0) 
23                     printf ("%ld ", tableau[i]);
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.

Ou plus simplement et efficacement:

1  void premiers(int tableau[], long tailleTableau)
 2  {
 3    long i, j;
 4 
 5    tableau[0] = tableau[1] = 0;
 6    for (i = 2 ; i < tailleTableau ; i++) tableau[i] = 1;
 7
 8    for (i = 2 ; i < sqrt(tailleTableau) ; i++)
 9      if (tableau[i])
10        for (j = i*i ; j < tailleTableau ; j += i)
11          tableau[j] = 0;
12
13    for (i = 0 ; i < tailleTableau ; i++)
14      if (tableau[i]) printf ("%d ", i);
15
16  }

• ligne 1 : le tableau n'est pas censé être initialisé. tableau[i] contiendra 1 si i est premier, 0 sinon.
• ligne 5 : 0 et 1 ne sont pas premiers
• ligne 6 : les nombres > 2 sont premiers jusqu'à preuve du contraire.
• ligne 9,10,11 : si i est premier, on marque tous ses multiples comme non premiers :i*2, i*3, ... jusqu'à n. On commence en fait à i*i puisque les i*k avec k < i ont déjà été eliminés en tant que multiples de k.

[modifier] 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.

[modifier] Liens internes

• Crible d'Atkin

[modifier] Liens externes

• Animation interactive (JavaScript)
• Crible d'Ératosthène (Java)

• Portail des mathématiques