RA-GAlgorithmes récurrents et arithmétiques

Primalité d'un entier naturel — test par division

Idée directrice

Un entier naturel $n>1$ est premier (test de primalité) s'il n'admet aucun diviseur $d$ dans $[2..\lfloor\sqrt{n}\rfloor]$ . Le corrigé bac 2015 code ce test avec une boucle mod jusqu'à la racine carrée.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Premier / primalité »

« racinecarré(r) »

« r mod d »

Sujet principal

Exercice — dans l'esprit des sujets d'informatique

3 questionsCorrigé masqué

Écrire l'algorithme itératif d'un test de primalité Premier(r) pour un entier naturel $r>1$ : on incrémente un diviseur $d$ tant que $r\bmod d \neq 0$ et $d \le \sqrt{r}$ .
Pourquoi la borne $\lfloor\sqrt{r}\rfloor$ (racine) suffit-elle ? Relier au facteur complémentaire $r/d$ .
Un programme retient un entier $t[i]$ lorsque Premier(t[i]) et Premier((t[i]-1) div 2) sont tous deux vrais. En une phrase, quelle propriété de $t[i]$ cette double condition teste-t-elle ? Donner un exemple.

Voir la correction commentéeAprès avoir posé votre démarche

1. Test de primalité itératif.

DEF FN Premier (r : entier) : booléen
Variables d : entier
Début
  d ← 1
  Répéter
    d ← d + 1
  Jusqu'à (r mod d = 0) ou (d > racinecarré(r))
  Retourner (d > racinecarré(r))
Fin

Aucun diviseur trouvé avant la racine ⇒ l'entier est premier.

2. Si un facteur $d>\sqrt{r}$ divisait $r$ , le cofacteur $r/d$ serait un diviseur $<\sqrt{r}$ déjà rencontré. D'où la borne.

3. (t[i]-1) div 2 : on exige que $(t[i]-1)/2$ soit lui aussi premier. $t[i]$ est alors un nombre premier dit « sûr » : $t[i] = 2q + 1$ avec $q$ premier. Exemples : 7 (car 3 est premier), 11 (car 5), 23 (car 11) ; mais pas 13, car $(13-1)/2 = 6$ n'est pas premier.

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 01

Drill RA-G.1 — Compter les diviseurs

5 questionsCorrigé masqué

Pour décider si un entier naturel $N \geq 2$ est premier, trois propositions comptent dans s les valeurs de $I$ telles que N mod I = 0 :

P1 : s ← 0 ; Pour I de 1 à N faire Si N mod I = 0 alors s ← s+1 FinSi FinPour ; Premier ← (s = 2)
P2 : s ← 0 ; Pour I de 2 à N faire Si N mod I = 0 alors s ← s+1 FinSi FinPour ; Premier ← (s = 0)
P3 : s ← 0 ; Pour I de 2 à N-1 faire Si N mod I = 0 alors s ← s+1 FinSi FinPour ; Premier ← (s = 0)

Pour $N = 7$ puis $N = 9$ , donner la valeur finale de s et le résultat rendu par chaque proposition.
En déduire les propositions correctes et corriger celle qui ne l'est pas.

Voir la correction commentéeAprès avoir posé votre démarche

1. $N = 7$ : P1 compte $I = 1$ et $I = 7$ , s = 2, rend Vrai ; P2 compte $I = 7$ , s = 1, rend Faux (à tort) ; P3 ne compte rien, s = 0, rend Vrai. $N = 9$ : P1 compte 1, 3, 9, s = 3, Faux ; P2 compte 3 et 9, s = 2, Faux ; P3 compte 3, s = 1, Faux.

2. P1 et P3 sont correctes : un nombre premier a exactement deux diviseurs (1 et lui-même), donc s = 2 sur [1..N], ou aucun diviseur propre, donc s = 0 sur [2..N-1]. P2 est fausse parce que $I = N$ divise toujours $N$ : sur [2..N] un premier donne s = 1, jamais 0. La corriger : Premier ← (s = 1), ou arrêter la boucle à $N-1$ (ou à $\lfloor\sqrt N\rfloor$ ).

Méthode / Automatismes

Toujours borner par la racine ; traiter $r\le 1$ à part.
Le mod révèle un diviseur ; dès le premier hit, ce n'est pas un nombre premier.

Pièges classiques

Boucler jusqu'à $r$ inclus ; confondre primalité et décomposition en facteurs premiers (autre module du même chapitre).