RA-JAlgorithmes récurrents et arithmétiques

Modules PGCD et PGCDTous — spécification algorithmique

Idée directrice

Spécifier deux modules arithmétiques : `PGCD(a,b)` (algorithme d'Euclide par `mod`) et `PGCDTous` qui calcule le PGCD d'une liste d'entiers naturels en réutilisant Euclide.

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

« modules PGCD et PGCDTous »

« solution algorithmique »

« Vérifpremier »

Sujet principal

Exercice — dans l'esprit des sujets d'informatique

3 questionsCorrigé masqué

On demande une solution algorithmique de deux modules `PGCD` et `PGCDTous` (devoir i-c3-01) pour des entiers naturels — chapitre bases/arithmétique, pas récursivité.

Écrire le module `PGCD(a,b)` selon l'algorithme d'Euclide itératif (`mod` jusqu'à reste nul) pour deux entiers.
Écrire le module `PGCDTous(T[1..n])` qui calcule le PGCD de tous les entiers du vecteur en enchaînant Euclide : $g\leftarrow T[1]$ puis $g\leftarrow PGCD(g,T[i])$ .
Trace : `PGCDTous([12,18,30])` — valeurs successives de l'accumulateur.

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

1. Euclide.

```
DEF FN PGCD(a, b : entier) : entier
Variables r : entier
Début
TantQue b ≠ 0 faire
r ← a mod b ; a ← b ; b ← r
FinTantQue
Retourner a
Fin
```

2. PGCDTous.

```
DEF FN PGCDTous(T : vect ; n : entier) : entier
Variables g, i : entier
Début
g ← T[1]
Pour i de 2 à n faire
g ← PGCD(g, T[i])
FinPour
Retourner g
Fin
```

3. $g=12$ ; $PGCD(12,18)=6$ ; $PGCD(6,30)=6$ . Résultat 6.

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

Entraînement 01 / 01

Drill RA-J.1 — Définition premier

1 questionCorrigé masqué

Le devoir i-c3-01 rappelle : un entier naturel est premier s'il a exactement deux diviseurs (1 et lui-même). En une phrase, pourquoi la boucle de test doit s'arrêter au plus à $\lfloor\sqrt{N}\rfloor$ (lien diviseur/facteur) ?

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

Si $N$ a un diviseur $d>\sqrt{N}$ , alors $N/d$ est un autre diviseur $<\sqrt{N}$ déjà rencontré. Donc il suffit de chercher jusqu'à $\lfloor\sqrt{N}\rfloor$ pour décider de la primalité (même idée que le corrigé 2015 `Premier` et le rappel i-c3-01).

Méthode / Automatismes

`PGCD` de plus de deux nombres = composition associative.
Ne pas confondre avec le test de primalité (`Vérifpremier` du même devoir).

Pièges classiques

Réécrire Euclide en récursif sans cas de base ; initialiser `g` à 0.