Algoritmul lui Euclid

Cel mai mare divizor comun, prescurtat CMMDC, al două numere este cel mai mare număr care le divide pe amândouă. Algoritmul lui Euclid folosește faptul că $\mathrm{cmmdc}(a,b)=\mathrm{cmmdc}(b,a\mathrm{mod}b)$ pentru $b\ne 0$. Repetăm până când al doilea număr devine zero; primul este răspunsul.

În Python, 18 % 12 dă 6, apoi 12 % 6 dă 0; algoritmul lui Euclid se oprește cu CMMDC egal cu 6.

Algoritmul lui Euclid pornește de la observația că $\mathrm{cmmdc}(a,b)=\mathrm{cmmdc}(b,a\mathrm{mod}b)$ pentru $b\ne 0$ și că $\mathrm{cmmdc}(a,0)=a$. Un divizor comun al lui $a$ și $b$ divide și restul $r=a-bq$, iar un divizor comun al lui $b$ și $r$ divide $a=bq+r$; perechile au deci aceiași divizori comuni. Restul scade strict la fiecare pas, așa că algoritmul se oprește, iar numărul de împărțiri este cel mult proporțional cu numărul de cifre ale lui $b$.

Exemplul 1 — $\mathrm{cmmdc}(48;18)$. Se notează perechea după fiecare iterație.

1. $48=2\cdot 18+12$, deci perechea devine $(18;12)$.
2. $18=1\cdot 12+6$, deci perechea devine $(12;6)$.
3. $12=2\cdot 6+0$, deci perechea devine $(6;0)$.
4. Al doilea număr este 0, ciclul se oprește; rezultatul este primul număr, 6.

#include <iostream>
using namespace std;
int main() {
    int a = 48, b = 18;
    while (b != 0) {
        int rest = a % b;
        a = b;
        b = rest;
    }
    cout << a;
    return 0;
}

Programul afișează 6. Ordinea atribuirilor contează: dacă ai scrie întâi a = b, restul s-ar calcula cu valoarea nouă și rezultatul ar fi greșit.

Exemplul 2 — fracție ireductibilă. Fracția $\frac{84}{126}$ se simplifică prin $\mathrm{cmmdc}(84;126)$. Pașii: $126=1\cdot 84+42$, apoi $84=2\cdot 42+0$, deci cmmdc este 42 și fracția devine $\frac{84:42}{126:42}=\frac{2}{3}$. Două numere sunt prime între ele (coprime) dacă $\mathrm{cmmdc}=1$; de exemplu pentru $(14;25)$ resturile sunt 14, 11, 3, 2, 1, 0, deci cmmdc este 1.

Exemplul 3 — o problemă cu răspuns prin cmmdc. Un dreptunghi de $84\times 126$ unități se acoperă exact cu pătrate egale, fără rest. Cea mai mare latură posibilă este divizor comun al lui 84 și 126, deci cmmdc, adică 42. Atunci încap $84/42=2$ pătrate pe lățime și $126/42=3$ pe lungime, în total $2\cdot 3=6$ pătrate. Orice latură mai mică, precum 21 sau 14, este tot un divizor comun și ar da mai multe pătrate: 24 în cazul laturii 21.

Câte împărțiri face algoritmul. Numărul de iterații crește cu logaritmul numerelor, nu cu valoarea lor. Cazul cel mai lung apare când împărțirile dau câturi 1, adică la termeni consecutivi ai șirului lui Fibonacci: pentru $(89;55)$ se fac nouă împărțiri, cu resturile 34, 21, 13, 8, 5, 3, 2, 1, 0, iar nicio pereche cu al doilea număr mai mic decât 55 nu cere mai mult de opt. De aceea, chiar pentru numere de ordinul $10^{18}$, algoritmul face cel mult câteva sute de împărțiri.

Varianta prin scăderi folosește egalitatea $\mathrm{cmmdc}(a,b)=\mathrm{cmmdc}(a-b,b)$ pentru $a>b>0$. Pentru $(48;18)$ se obțin perechile $(30;18)$, $(12;18)$, $(12;6)$ și $(6;6)$; ciclul se oprește când numerele sunt egale, iar rezultatul este 6. Varianta cu restul înlocuiește mai multe scăderi consecutive printr-o singură împărțire; pentru $(1000000;1)$ scăderile ar face un milion de pași, iar împărțirea unul singur.

Ideea. Dacă $a=b\cdot q+r$, cu restul $r<b$, atunci $a$ și $b$ au exact aceiași divizori comuni ca $b$ și $r$. De aceea poți înlocui perechea $(a,b)$ cu $(b,r)$ fără să schimbi cel mai mare divizor comun. Numerele scad la fiecare pas, așa că după câțiva pași restul devine 0. În acel moment perechea este $(d,0)$, iar $\mathrm{cmmdc}(d,0)=d$.

Varianta cu împărțiri, în pseudocod, cu convențiile din subiectele de Bacalaureat:

citește a, b (numere naturale)
┌cât timp b ≠ 0 execută
│  r ← a % b
│  a ← b
│  b ← r
└■
scrie a

Dacă la început $a<b$, primul pas doar le interschimbă: pentru $a=210$ și $b=588$, restul este 210, iar perechea devine $(588,210)$. Dacă $b=0$ de la început, algoritmul afișează $a$, ceea ce e corect, pentru că orice număr divide 0.

Varianta cu scăderi funcționează numai pentru numere nenule: dacă unul este 0, scăderea nu îl mai modifică pe celălalt, iar bucla nu se oprește. Cele două variante, pentru comparație:

Varianta recursivă. Relația $\mathrm{cmmdc}(a,b)=\mathrm{cmmdc}(b,a\%b)$ se scrie direct ca funcție recursivă:

int cmmdc(int a, int b) {
    if (b == 0)
        return a;
    return cmmdc(b, a % b);
}

De la cmmdc la cmmmc. Pentru numere nenule, $\mathrm{cmmdc}(a,b)\cdot \mathrm{cmmmc}(a,b)=a\cdot b$. Calculul a * b / d poate depăși valoarea maximă a tipului int chiar când rezultatul încape, de aceea împarți întâi: a / d * b.

În Python (clasa a IX-a, programa nouă). Programa nouă de clasa a IX-a cere ambele variante ale algoritmului, scrise în Python. Varianta cu împărțiri arată așa:

def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(cmmdc(588, 210))

42

Exemple suplimentare

Exemplul 4 — cel mai mic multiplu comun. Din relația $\mathrm{cmmdc}(a;b)\cdot \mathrm{cmmmc}(a;b)=a\cdot b$ rezultă $\mathrm{cmmmc}(48;18)=\frac{48\cdot 18}{6}=144$. Două lumini clipesc la 48 și la 18 de secunde; ele clipesc din nou împreună după 144 de secunde. În program se calculează a / d * b, nu a * b / d: pentru $a=100000$ și $b=99999$ produsul este 9 999 900 000 și depășește valoarea maximă a tipului int, 2 147 483 647.

Exemple rezolvate

Exemplul 1: urmărirea împărțirilor. Calculează $\mathrm{cmmdc}(588,210)$ cu varianta cu împărțiri și scrie valorile lui $a$, $b$ și $r$ la fiecare pas.

1. $588=210\cdot 2+168$, deci $r=168$, iar perechea devine $(210,168)$.
2. $210=168\cdot 1+42$, deci $r=42$, iar perechea devine $(168,42)$.
3. $168=42\cdot 4+0$, deci $r=0$, iar perechea devine $(42,0)$. Bucla se oprește.

#include <iostream>
using namespace std;

int main() {
    int a, b, r;
    cin >> a >> b;
    while (b != 0) {
        r = a % b;
        cout << a << " " << b << " " << r << "\n";
        a = b;
        b = r;
    }
    cout << "cmmdc = " << a << "\n";
    return 0;
}

Pentru intrarea 588 210, programul afișează:

588 210 168
210 168 42
168 42 0
cmmdc = 42

Verificare: $588=2^2\cdot 3\cdot 7^2$ și $210=2\cdot 3\cdot 5\cdot 7$, deci $\mathrm{cmmdc}=2\cdot 3\cdot 7=42$.

Exemplul 2: aceleași numere, prin scăderi. Câte scăderi face varianta cu scăderi pentru 588 și 210?

1. Perechile sunt: (378, 210), (168, 210), (168, 42), (126, 42), (84, 42), (42, 42).
2. Sunt 6 scăderi, față de 3 împărțiri. Primele două scăderi țin locul împărțirii $588=210\cdot 2+168$, iar ultimele trei, al împărțirii $168=42\cdot 4$.

#include <iostream>
using namespace std;

int main() {
    int a, b, pasi = 0;
    cin >> a >> b;            // a, b nenule
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
        pasi++;
    }
    cout << a << " " << pasi << "\n";
    return 0;
}

Pentru intrarea 588 210, programul afișează:

42 6

Exemplul 3: cmmmc. Calculează $\mathrm{cmmmc}(84,126)$.

1. $126=84\cdot 1+42$ și $84=42\cdot 2+0$, deci $\mathrm{cmmdc}(84,126)=42$.
2. $\mathrm{cmmmc}=84/42\cdot 126=2\cdot 126=252$.

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << a / cmmdc(a, b) * b << "\n";
    return 0;
}

Pentru intrarea 84 126, programul afișează:

252

Exemplul 4: simplificarea unei fracții. Se citesc numărătorul și numitorul unei fracții, numere naturale nenule. Afișează fracția ireductibilă egală cu ea. Pentru $1350/2025$: $\mathrm{cmmdc}(1350,2025)=675$, deci fracția devine $2/3$.

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int x = a, y = b;
    while (y != 0) {          // cmmdc pe copii, ca a si b sa ramana neschimbate
        int r = x % y;
        x = y;
        y = r;
    }
    cout << a / x << "/" << b / x << "\n";
    return 0;
}

Pentru intrarea 1350 2025, programul afișează:

2/3

Exemplul 5: nivel de examen, perechi de numere prime între ele. Scrie subprogramul prime, care primește prin parametrii $a$ și $b$ două numere naturale nenule și returnează 1 dacă ele sunt prime între ele, sau 0 altfel. Folosește-l ca să afli câte perechi $(x,y)$, cu $1\le x<y\le 30$, sunt formate din numere prime între ele.

1. Două numere sunt prime între ele dacă cmmdc lor este 1, deci subprogramul calculează cmmdc cu algoritmul lui Euclid și compară rezultatul cu 1.
2. Programul parcurge toate perechile cu $x<y$ și le numără pe cele pentru care subprogramul returnează 1.

#include <iostream>
using namespace std;

int prime(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a == 1;
}

int main() {
    int nr = 0;
    for (int x = 1; x <= 30; x++)
        for (int y = x + 1; y <= 30; y++)
            if (prime(x, y))
                nr++;
    cout << nr << "\n";
    return 0;
}

Programul afișează:

277

Subprogramul lucrează pe copiile parametrilor (transmiși prin valoare), așa că x și y din main nu se modifică.

La urmărirea fragmentelor, notează perechea $(a;b)$ după fiecare iterație, nu doar restul. Expresia a % b nu se evaluează pentru b = 0. Algoritmul poate fi cerut și ca test de coprimalitate sau ca număr de iterații. Dacă ordinea numerelor este inversată, de exemplu $(18;48)$, prima iterație doar le schimbă între ele: $18\mathrm{mod}48=18$, perechea devine $(48;18)$ și se continuă ca mai sus. Variabila k din secvențele de examen numără iterațiile, nu resturile nenule: numărul ei este cu unul mai mare decât numărul resturilor nenule, pentru că ultima iterație produce restul 0. Când apar trei numere, cmmdc se aplică de două ori: $\mathrm{cmmdc}(a;b;c)=\mathrm{cmmdc}(\mathrm{cmmdc}(a;b);c)$.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int a = 84, b = 36, k = 0;
while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
    k++;
}
cout << a << ' ' << k;

• a) 12 2
• b) 12 3
• c) 6 2
• d) 36 1

Răspunsul corect este a). Prima iterație: $r=84\mathrm{mod}36=12$, perechea devine $(36;12)$ și $k=1$. A doua: $r=36\mathrm{mod}12=0$, perechea devine $(12;0)$ și $k=2$. Ciclul se oprește cu $b=0$ și se afișează valoarea lui $a$, adică 12, urmată de numărul de iterații, 2. Varianta d) apare dacă se oprește ciclul după prima iterație.

Al doilea exemplu în formatul examenului. Varianta recursivă a algoritmului. Ce se afișează?

int f(int a, int b) {
    return b == 0 ? a : f(b, a % b);
}
cout << f(35, 15) << ' ' << f(15, 35);

Răspunsul este 5 5. Apelul f(35, 15) ajunge la f(15, 5), apoi la f(5, 0), care întoarce 5. Apelul f(15, 35) calculează $15\mathrm{mod}35=15$ și devine f(35, 15), adică același lanț; ordinea argumentelor schimbă numărul de apeluri, nu rezultatul. Primul apel face trei apeluri în total, iar al doilea patru, deoarece primul pas doar inversează argumentele.

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen numește explicit algoritmul lui Euclid, la „Algoritmi elementari”, alături de divizibilitate și numerele prime (anexa 2 la OMECTS 4800/2010). Algoritmul poate apărea în pseudocod la Subiectul al II-lea, unde se cer valoarea afișată, date de intrare și un algoritm echivalent, sau într-un subprogram cerut la Subiectul al III-lea, care este formatul probei din iunie–iulie 2026. Formatul descris este cel din 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.

Pe programa școlară veche, determinarea cmmdc și a cmmmc este la clasa a IX-a, la prelucrarea numerelor (OMECI 5099/2009); programa nouă de clasa a IX-a cere explicit algoritmul lui Euclid cu scăderi repetate și cu împărțiri repetate (OMEC 6930/2025, anexa 42).

Greșeli frecvente

• Greșit: rezultatul este ultimul rest zero.
  Corect: este ultimul rest nenul, aflat în a; la final b este 0, deci afișarea lui b în loc de a este greșită.
• Greșit: se poate calcula a % b după ce b a devenit zero.
  Corect: bucla se oprește înainte.
• Greșit: CMMDC al lui 48 și 18 este 12.
  Corect: este 6.
• Greșit: varianta cu scăderi merge și pentru un număr egal cu 0.
  Corect: dacă $a=0$ și $b>0$, bucla while (a != b) scade la nesfârșit 0 din $b$, fără să îl schimbe; varianta cu scăderi se folosește numai pentru numere nenule, iar cea cu împărțiri tratează corect și cazul $b=0$.
• Greșit: ordinea atribuirilor nu contează.
  Corect: scrierea a = b; b = a % b; calculează restul cu valoarea nouă a lui a, adică $b\%b=0$; restul trebuie salvat înainte, într-o variabilă r.
• Greșit: algoritmul poate modifica liber valorile citite.
  Corect: algoritmul modifică a și b; dacă îți mai trebuie după aceea (de exemplu, la simplificarea fracției sau la cmmmc), lucrezi pe copii sau într-un subprogram cu parametri transmiși prin valoare.
• Greșit: a * b / d este un calcul sigur al cmmmc.
  Corect: poate depăși tipul int; scrie a / d * b sau folosește long long.

Înainte și după

Întrebări frecvente