Énoncé
Saisir deux entiers A et B strictement positifs avec une saisie contrôlée. Calculer leur plus grand commun diviseur par divisions successives.
Exemples et cas limites
Saisissez ces valeurs dans la console pour vérifier votre résultat :
Entrée
A = 48 B = 18
Sortie attendue
6
Entrée
A = 12 B = 18
Sortie attendue
6
Entrée
A = -48 B = 18 A = 48 B = 18
Sortie attendue
6
Entrée
A = 0 B = 0 A = 12 B = 18
Sortie attendue
6
Code algorithmique
| 1 | algorithme pgcd_euclide |
| 2 | debut |
| 3 | repeter |
| 4 | ecrire("A = ") |
| 5 | lire(a) |
| 6 | ecrire("B = ") |
| 7 | lire(b) |
| 8 | jusqua a > 0 et b > 0 |
| 9 | // compléter le traitement demandé dans l’énoncé. |
| 10 | fin |
| 1 | algorithme pgcd_euclide |
| 2 | debut |
| 3 | repeter |
| 4 | ecrire("A = ") |
| 5 | lire(a) |
| 6 | ecrire("B = ") |
| 7 | lire(b) |
| 8 | jusqua a > 0 et b > 0 |
| 9 | tant_que b ≠ 0 faire |
| 10 | reste ← a mod b |
| 11 | a ← b |
| 12 | b ← reste |
| 13 | fin_tant_que |
| 14 | ecrire_nl(a) |
| 15 | fin |
Méthode
- Redemander A et B jusqu’à obtenir A > 0 ET B > 0.
- Remplacer (A, B) par (B, A MOD B) jusqu’à B = 0.
Comprendre la correction
Déroulement sur un exemple
- Avec A = 48 et B = 18, 48 MOD 18 = 12. On remplace le couple par (18, 12).
- 18 MOD 12 = 6, puis 12 MOD 6 = 0. Les couples deviennent (12, 6), puis (6, 0).
- B vaut 0 : le dernier diviseur non nul, A = 6, est le PGCD. Remplacer A par A MOD B conserve les diviseurs communs.
Erreurs à éviter
- Calculez reste avant a ← b, sinon vous perdez l’ancienne valeur de A.
- La sortie est A, pas B : B vaut 0 à la fin.