1. Le crible : présentation
L'idée est simple, pour obtenir les nombres premiers inférieurs à n.
- Écrire tous les entiers de 2 à n,
- Enlever (ou barrer) les multiples de 2 sauf 2,
- Récupérer le plus petit nombre nom barré, c'est à dire 3, et barrer les multiples de 3 sauf 3,
- etc...
- Test d'arrêt : On s'arrête dès q'on a atteint la racine carrée de n.
Voici une jolie animation du crible.
2. Le crible : démonstration.
Pour la démonstration de ce crible, il faut tout d'abord rappeler le théorème fondamental de l'arithmétique.
- Théorème fondamental de l'arithmétique. (En savoir plus. )
Tout nombre entier naturel n > 1 peut s'écrire comme un produit de nombres premiers, et cette représentation est unique, à l'ordre des facteurs premiers près. Soit en d'autres termes :
n = q1 a1 × q2 a2 × q3 a3 × ..... × qr ar ; avec les qi premiers distincts et les ai entiers positifs.
Supposons donc que l'entier n est composé et que tous les nombres premiers p qui divisent n satisfont à la condition :
(C1) : √n < p ≤ n .
Alors si un certain nombre premier p divise n et satisfait à la condition (C1), on peut écrire n =p×b pour un certain entier b >1.
Mais alors, b divise aussi n et b = n / p < n / √n = √n.
On a ainsi trouvé b, un diviseur de n qui possède au moins un facteur premier inférieur à √n, ce qui est une contradiction.
Donc : un nombre naturel n qui n'est divisible par aucun nombre premier p ≤ √n est automatiquement lui-même premier.
C'est avec cette règle qu'Eratosthène a construit son crible.
Dans le crible d'Eratosthène, ausitôt que l'on arrive à l'étape où le plus petit nombre qui n'a pas été rayé est supérieur à √n, on arrête le processus et on est ainsi assuré que tous les nombres non rayés dans la liste sont des nombres premiers.
3. Le crible : Exemple.
Par exemple, 223 n'est divisible, ni par 2, ni par 3, ni par 5, ni par 7, ni par 11, ni par 13.
Il est inutile de vérifier s'il est divisible par 17 car 17² > 289 > 223.
On en déduit que le nombre 223 est premier.
4. Le crible : programmation.
Le site scriptol en propose de nombreux