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}$ (esprit corrigé bac 2015, `DEF FN Premier`).
Pourquoi la borne $\lfloor\sqrt{r}\rfloor$ (racine) suffit-elle ? Relier au facteur complémentaire $r/d$ .
Le corrigé 2015 utilise `Premier(t[i])` et `Premier((t[i]-1) div 2)` pour ranger certains entiers. En une phrase, que teste la seconde condition sur l'entier $t[i]$ (lien avec un diviseur particulier) ?

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

1. Test de primalité itératif (corrigé 2015).

```
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 demande aussi que $(t[i]-1)/2$ soit premier (filtre supplémentaire du rangement 2015 — couple d'entiers liés par une relation de diviseur/moitié).

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

Entraînement 01 / 01

Drill RA-G.1 — Compter les diviseurs

1 questionCorrigé masqué

Trois propositions comptent avec un diviseur $I$ les cas `N mod I = 0` pour décider si un entier naturel $N$ est premier (devoir i-s1-01). La bonne version boucle de 2 à $N-1$ (ou jusqu'à la racine) et exige un compteur de diviseurs nul. Pourquoi `s=1` ou une boucle jusqu'à $N$ sont-elles fausses ?

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

Jusqu'à $N$ inclus, $N\bmod N=0$ incrémente toujours le compteur : on ne peut pas conclure avec `s=1`. De 2 à $N-1$ , un nombre premier n'a aucun diviseur propre : il faut `s=0` (compteur de `N mod I = 0` resté nul). C'est le critère de primalité du devoir i-s1-01 (proposition V/F sur `verif`). Les variantes qui bouclent de 1 à $N$ ou concluent `s=1`/`s=2` confondent le cas « $N$ se divise lui-même » avec la définition d'un entier naturel premier.

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