CMMDC — Algoritmul lui Euclid

De ce contează?

Vrei să tai o tablă de 84 cm și una de 36 cm în bucăți egale, cât mai mari, fără risipă. Răspunsul este cel mai mare număr care divide ambele lungimi — CMMDC. Algoritmul lui Euclid îl calculează în câteva pași și este folosit de mai bine de 2300 de ani.

Ce este CMMDC?

Cel Mai Mare Divizor Comun al lui a și b este cel mai mare număr care divide exact ambele.

Exemplu: CMMDC(84, 36) = 12, deoarece 84 = 12 × 7 și 36 = 12 × 3.

Algoritmul lui Euclid

Proprietate cheie: CMMDC(a, b) = CMMDC(b, a % b)

Aplicăm repetat această proprietate până când b devine 0:

CMMDC(84, 36):
  84 % 36 = 12 → CMMDC(36, 12)
  36 % 12 = 0  → CMMDC(12, 0)
  b = 0        → rezultat: 12

Observația-cheie

La fiecare pas, cel mai mic argument se reduce cu cel puțin jumătate. Asta garantează că algoritmul se termină rapid — în O(log(min(a,b))) pași, chiar și pentru numere cu milioane de cifre.

Implementare C++ — iterativă

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    cout << "CMMDC(" << a << ", " << b << ") = " << cmmdc(a, b) << endl;
    return 0;
}

Exemplu: Input 84 36 → CMMDC(84, 36) = 12

Varianta recursivă

int cmmdc(int a, int b) {
    if (b == 0) return a;       // caz de baza
    return cmmdc(b, a % b);     // pas recursiv
}

Elegantă și compactă, dar consumă memorie de stivă proporțional cu numărul de pași.

Complexitate

Caz	Timp	Spațiu
Iterativ	O(log(min(a,b)))	O(1)
Recursiv	O(log(min(a,b)))	O(log n) — stivă

Vizualizare

Urmărește cum resturile succesive scad până când b devine 0 — ultima valoare nenulă este CMMDC:

Greșeli frecvente

Greșeala 1: Confunzi ordinea la pasul de reducere. CMMDC(a, b) = CMMDC(b, a % b) — noul prim argument este b, nu a % b.

Greșeala 2: Aplici algoritmul cu a = 0. CMMDC(0, b) = b prin definiție. Dacă inputul poate conține 0, verifică separat.

Greșeala 3: La varianta iterativă, suprascrii a înainte de a calcula rest. Dacă scrii a = b; b = a % b, al doilea a e deja modificat — rezultat greșit. Salvează rest = a % b mai întâi.