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

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

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é.

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Exemple 1 — $n = 37$

Étape 1 —

Calculer

\lfloor\sqrt{n}\rfloor

et dresser (ou utiliser) la liste des premiers jusqu'à cette borne.

$\lfloor\sqrt{37}\rfloor = 6$ . Premiers à tester : $2, 3, 5$ .

Étape 2 —

Tester la divisibilité de

n

par chaque premier

p

de la liste : calculer

n \mod p

$37$ est impair ( $2 \nmid 37$ ). $3+7=10$ non multiple de $3$ . $37$ ne finit pas par $0$ ou $5$ ( $5 \nmid 37$ ).

Étape 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é.

Aucun premier $\leq 6$ ne divise $37$ , donc $37$ est premier.

Application guidée

Exemple 2 — $n = 91$

Application autonome 1

Exemple 3 — $n = 101$

Application autonome 2

Exemple 4 — $n = 143$

Application autonome 3

Exemple 5 — $n = 127$

Crée ton compte gratuit pour accéder à la fiche et aux exercices