Le crible d'Ératosthène (IIIe av. JC).
La façon la plus simple de trouver des nombre premiers est un algorithme appelé, crible d'Eratosthène (IIIe av. JC).
ÉRATOSTHÈNE de Cyrène est un astronome, géographe et mathématicien, 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.
C'est le mathématicien norvégien Brun Vigo (1885 - 1978) qui introduit en 1919 la première étude théorique du crible d'Eratosthène, et en crée un raffinement appelé crible de Brun.
1. Le crible.
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 trouvée sur internet.
Image présentant la méthode du crible d'Eratosthène, Source.
2. La 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.
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 = q_1^{a_1} × q_2^{a_2} × q_3^{a_3} × ..... × q_r^{a_r} $$
avec les \(q_i\) premiers distincts et les \(a_i\) entiers positifs.
Supposons donc que l'entier \(n\) est composé et que tous les nombres premiers \(p\) qui divisent \(n\) satisfont à la condition :
$$(C1) ~~:~~ \sqrt{n} < p ≤ n $$
Alors si un certain nombre premier \(p\) divise \(n\) et satisfait à la condition (C1), on peut écrire \(n =p\times b\) pour un certain entier \(b >1\).
Mais alors, \(b\) divise aussi \(n\) et
$$b = \dfrac{n}{p} < \dfrac{n}{\sqrt{n}} = \sqrt{n}$$
On a ainsi trouvé \(b\), un diviseur de \(n\) qui possède au moins un facteur premier inférieur à \(\sqrt{n}\), ce qui est une contradiction.
Donc : un nombre naturel \(n\) qui n'est divisible par aucun nombre premier \( p ≤ \sqrt{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, par exemple.
1. L'algorithme:
- Construire une liste de tous les entiers supérieurs à 1 et inférieurs ou égal à n.
- Supprimer les multiples de tous les premiers inférieurs ou égal à la racine carrée de n,
- ensuite, les nombres qui restent sont premiers.
2. En code Scriptol :
- int n = 50
- array a
- int i, j
- a[1] = 0
- for i in 2 .. n let a[i] = 1
- int p = 2
- while (p * p) <= n
- j = p * p
- while j <= n
- a[j] = 0
- let j + p
- do
- p + 1
- until a[p] = 1
- /while
- Afficher les premiers:
- for int x in 0 .. n
- if a[x] echo " ", x
- /for print
⇒ Pour en savoir plus sur le personnage, visitez la page : Eratosthène.
