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

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