Appliquer le crible d’Ératosthène
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Le crible d'Ératosthène permet de déterminer tous les nombres premiers inférieurs ou égaux à un entier $ N $. On écrit tous les entiers de $ 2 $ à $ N $, puis on élimine les multiples de chaque nombre premier trouvé.
- Étape 1 : écrire la liste de tous les entiers de $ 2 $ à $ N $ (le nombre $ 1 $ n'est pas premier, on ne l'inscrit pas).
- Étape 2 : le premier nombre non barré est $ 2 $ ; il est premier. Barrer tous ses multiples : $ 4 $, $ 6 $, $ 8 $, ...
- Étape 3 : revenir au plus petit entier non barré suivant ; il est premier. Barrer tous ses multiples encore présents.
- Étape 4 : recommencer tant que le plus petit entier non barré $ p $ vérifie $ p \leqslant \sqrt{N} $ (c'est-à-dire $ p^{2} \leqslant N $).
- Étape 5 : dès que $ p^{2} > N $, on s'arrête : tous les entiers encore non barrés sont premiers.
Remarque
L'arrêt à $ \sqrt{N} $ s'appuie sur la propriété : tout entier non premier $ n>1 $ admet un diviseur premier inférieur ou égal à $ \sqrt{n} $. Si un nombre $ n \leqslant N $ avait survécu au crible jusqu'à $ \sqrt{N} $ tout en étant composé, il aurait un facteur premier $ p \leqslant \sqrt{n} \leqslant \sqrt{N} $ : il aurait donc déjà été barré.
Quand on barre les multiples de $ p $, il est inutile de commencer avant $ p^{2} $ : tout multiple $ kp $ avec $ k<p $ a déjà été éliminé comme multiple d'un nombre premier plus petit.
Le crible jusqu'à 30
Étape 1 : on cherche un majorant de $ \sqrt{30} $. Comme $ 5^{2}=25 $ et $ 6^{2}=36 $, on a $ 5<\sqrt{30}<6 $. Il suffit donc de barrer les multiples des nombres premiers inférieurs ou égaux à $ 5 $, c'est-à-dire $ 2 $, $ 3 $ et $ 5 $.
Étape 2 : $ 2 $ est premier. On barre $ 4 $, $ 6 $, $ 8 $, $ 10 $, ..., $ 30 $ (tous les nombres pairs après $ 2 $).
Étape 3 : le plus petit non barré suivant est $ 3 $, qui est premier. On barre les multiples de $ 3 $ encore présents à partir de $ 3^{2}=9 $ : $ 9 $, $ 15 $, $ 21 $, $ 27 $ (les autres, comme $ 6 $ ou $ 12 $, sont déjà barrés).
Étape 4 : le plus petit non barré suivant est $ 5 $, premier. On barre les multiples de $ 5 $ à partir de $ 5^{2}=25 $ : $ 25 $.
Étape 5 : le plus petit non barré suivant est $ 7 $. Or $ 7^{2}=49>30 $, donc on s'arrête. Tous les entiers restants sont premiers.
Conclusion : les nombres premiers inférieurs ou égaux à $ 30 $ sont :
Tester la primalité d'un entier par essais de division
Le crible liste tous les premiers jusqu'à $ N $. Pour décider de la primalité d'un seul entier, on procède plus directement par essais de division par les entiers $ d $ tels que $ d \leqslant \sqrt{n} $.
On veut savoir si $ n=221 $ est premier.
Étape 1 : $ 14^{2}=196 $ et $ 15^{2}=225 $, donc $ 14<\sqrt{221}<15 $. On teste les diviseurs jusqu'à $ 14 $ (en pratique, seulement les nombres premiers $ 2 $, $ 3 $, $ 5 $, $ 7 $, $ 11 $, $ 13 $).
Étape 2 : on divise successivement.
- $ 221 $ est impair : non divisible par $ 2 $.
- Somme des chiffres $ 2+2+1=5 $ : non divisible par $ 3 $.
- Dernier chiffre $ 1 $ : non divisible par $ 5 $.
- $ 221=7\times 31+4 $ : non divisible par $ 7 $.
- $ 221=11\times 20+1 $ : non divisible par $ 11 $.
- $ 221=13\times 17 $ : on a trouvé un diviseur.
Étape 3 : $ 221 $ admet le diviseur $ 13 $, donc $ 221 $ n'est pas premier : $ 221=\color{red}{13\times 17}\color{black} $.
Version algorithmique (programme du chapitre « Exemples d'algorithmes ») : on teste tous les diviseurs $ d $ depuis $ 2 $ tant que $ d^{2} \leqslant n $.
import math
def est_premier(n) :
if n < 2 :
return False
d = 2
while d * d <= n :
if n % d == 0 :
return False
d = d + 1
return TrueLa boucle s'arrête dès que $ d^{2}>n $, ce qui correspond exactement à l'arrêt à $ \sqrt{n} $. Pour $ n=221 $, elle renvoie False dès que $ d=13 $.
Remarque
Le crible peut aussi se programmer. On utilise une liste de booléens indiquant, pour chaque entier, s'il est encore considéré comme premier.
def crible(N) :
premier = [True] * (N + 1)
premier[0] = False
premier[1] = False
p = 2
while p * p <= N :
if premier[p] :
for m in range(p * p, N + 1, p) :
premier[m] = False
p = p + 1
return [k for k in range(2, N + 1) if premier[k]]Pour $ N=30 $, la fonction renvoie la liste $ [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] $, conforme au tableau ci-dessus. On y retrouve les deux optimisations du crible : on commence à barrer les multiples de $ p $ à partir de $ p^{2} $ (le range(p * p, ...)), et on arrête le barrage dès que $ p^{2}>N $, c'est-à-dire $ p>\sqrt{N} $ (le while p * p <= N).
Attention
Ne pas confondre les deux outils selon le besoin :
- pour obtenir la liste complète des premiers jusqu'à $ N $, utiliser le crible ;
- pour décider de la primalité d'un seul entier $ n $, les essais de division jusqu'à $ \sqrt{n} $ suffisent (voir aussi la méthode Démontrer qu'un entier est premier).
Erreur fréquente : poursuivre le barrage au-delà de $ \sqrt{N} $. C'est inutile : une fois les multiples de tous les premiers $ p \leqslant \sqrt{N} $ barrés, tous les entiers restants sont premiers. De même, oublier que $ 1 $ n'est pas premier (il n'a qu'un seul diviseur).