CMMDC — Algoritmul lui Euclid

De ce contează?

Vrei să tai două panglici, de 12 m și 18 m, în bucăți egale cât mai lungi, fără rest. Cea mai lungă bucată care „încape" exact în ambele este 6 m. Acel 6 este cel mai mare divizor comun — și există un truc vechi de 2000 de ani ca să-l afli rapid.

Ce este CMMDC

CMMDC(a, b) (cel mai mare divizor comun) este cel mai mare număr care divide exact și pe a, și pe b. Exemplu: cmmdc(12, 18) = 6.

Ideea lui Euclid

Observația genială: dacă scazi pe cel mic din cel mare, divizorul comun nu se schimbă. Mai eficient, folosim restul împărțirii:

cmmdc(a, b) = cmmdc(b, a % b), iar cmmdc(a, 0) = a.

Mereu înlocuim perechea cu una mai mică, cu același cmmdc, până restul devine 0.

Algoritm pas cu pas: cmmdc(48, 18)

`a`	`b`	`a % b`
48	18	12
18	12	6
12	6	0
6	0	— → stop

Când b ajunge 0, răspunsul e a = 6. Doar 3 pași.

Implementare 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;            // cand b a ajuns 0, a e raspunsul
}

int main() {
    cout << cmmdc(48, 18) << "\n";   // 6
    cout << cmmdc(17, 5) << "\n";    // 1 (prime intre ele)
    return 0;
}

Varianta recursivă

Aceeași idee, scrisă mai scurt:

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

Observația-cheie

Cele două variante fac exact aceiași pași. Cea iterativă e preferată la concurs pentru că nu consumă stiva de apeluri — sigură chiar și la numere foarte mari.

Complexitate

Caz	Timp	Spațiu
oricare	O(log(min(a, b)))	O(1)

Numerele scad rapid, deci Euclid e fulgerător chiar și pentru valori de ordinul miliardelor.

Greșeli frecvente

Capcane reale la CMMDC:

Inversezi atribuirile: scrii a = b; b = a % b; fără să salvezi restul întâi → a % b folosește deja noul a. Salvează restul într-o variabilă temporară.
Cazul cu 0: cmmdc(a, 0) = a, nu 0. Bucla while (b != 0) îl tratează corect.
Numere negative: la valori negative, lucrează pe abs(a), abs(b).
Overflow la CMMMC: când treci la cmmmc, a * b se poate sparge — vezi lecția CMMMC pentru ordinea corectă a operațiilor.

De reținut

cmmdc(a, b) = cmmdc(b, a % b), cu cmmdc(a, 0) = a.
Bucla se oprește când b = 0; răspunsul e ultimul a.
Cost O(log) — folosește Euclid, nu căutarea prin toți divizorii.