Tout savoir sur le crible d’Ératosthène

Comment connaitre tous les entiers inférieurs à n qui sont des nombres premiers ? Le crible d’Ératosthène apporte des réponses à cette question !

Un peu d’histoire

Erathostène a vécu au IIIème siècle avant Jésus-Christ. C’est un mathématicien, astronome et géographe. Il a été nommé à la tête de la bibliothèque d’Alexandrie. Il est resté célèbre pour son crible et pour avoir le premier mesuré le méridien terrestre. Ce crible est la façon la plus élémentaire pour trouver des nombres premiers.

Le crible d’Ératosthène

Décrivons l’algorithme sous jacent. Soit n un entier supérieur ou égal à 2 :

1. On écrit tous les entiers entre 2 et n
2. On enlève tous les multiples de 2, sauf 2
3. On prend ensuite tous les multiples du prochain nombre non barré, c’est à dire 3 et on enlève tous les multiples de 3 sauf 3.
4. On repète cette étape autant de fois que nécessaire
5. On s’arrête lorsqu’on a atteint \sqrt{n}

Cette jolie animation issue de Wikipedia résume bien l’algorithme :

Démonstration du critère d’arrêt

Rappelons le théorème des nombres premiers que nous avions vu dans l’article dédié à ce sujet. Tout entier n \geq m > 1 peut s’écrire

m = p_1^{\alpha_1}\times \ldots  \times p_k ^{\alpha_k}

Avec les p_i premiers distincts et \alpha_i entiers. Alors nécessairement :

• Soit m est premier
• Soit m peut s’écrire m = a b et nécessairement, on a a \leq \sqrt{n} ou b \leq \sqrt{n}. Car sinon le produit dépasserait n ! Donc tout nombre non premier plus grand que \sqrt{n} admet au moins un diviseur plus petit que \sqrt{n}

Et voilà, c’est principalement ce qu’il faut savoir sur le crible d’Ératosthène !