Comment tester la primalité d'un nombre ?

En vérifiant qu'aucun entier premier $p \leq \lfloor\sqrt{n}\rfloor$ ne divise $n$ (test de divisibilité exhaustif)

L'objectif

Décider si $n$ est premier en testant sa divisibilité par tous les premiers $\leq \lfloor\sqrt{n}\rfloor$ .

Le principe

Si $n$ est composé, l'un de ses facteurs premiers est $\leq \sqrt{n}$ ; tester tous les premiers jusqu'à $\lfloor\sqrt{n}\rfloor$ suffit.

La méthode

1
Calculer $\lfloor\sqrt{n}\rfloor$ et dresser (ou utiliser) la liste des premiers jusqu'à cette borne.
2
Tester la divisibilité de $n$ par chaque premier $p$ de la liste : calculer $n \mod p$ .
3
Si aucun premier $p \leq \lfloor\sqrt{n}\rfloor$ ne divise $n$ , conclure que $n$ est premier. Sinon, exhiber le diviseur et conclure que $n$ est composé.

Difficulté croissante de 1 à 5

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

En vérifiant qu'aucun entier premier p≤⌊n⌋p \leq \lfloor\sqrt{n}\rfloorp≤⌊n​⌋ ne divise nnn (test de divisibilité exhaustif)