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)

Que ferais-tu face à un exercice de ce type ?

Exemple 1 — $n = 37$

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, passons aux exercices.

Exercice d'exemple

Exemple 1 — $n = 37$

1

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

2

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

3

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

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment tester la primalité d'un nombre ?

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

Pour comprendre, passons aux exercices.

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