PGCD de A et B par décomposition simultanée — Algorithme Bac Informatique & Python

noscript{display:block;font-family:sans-serif;max-width:860px;margin:2rem auto;padding:1rem}pre{background:#090040;color:#ff9a00;padding:1rem;border-radius:8px;overflow:auto}

Accueil > Algorithmes > PGCD de A et B par décomposition simultanée

PGCD de A et B par décomposition simultanéeCalcule le PGCD en extrait les facteurs premiers communs à A et B.Pseudocode OfficielFonction pgcd(a, b : entier) : entier DÉBUT d ← 2, p ← 1 Tant que a ≠ 1 et b ≠ 1 Faire Si a mod d = 0 et b mod d = 0 Alors p ← p * d, a ← a div d, b ← b div d Sinon Si a mod d = 0 Alors a ← a div d Sinon Si b mod d = 0 Alors b ← b div d Sinon d ← d + 1 Fin Si Fin Tant que Retourner p FIN