Cum se calculează cmmdc în C++?

Cu algoritmul lui Euclid: cât timp b nu e zero, înlocuiești (a, b) cu (b, a % b), iar răspunsul este a. Pentru cmmmc folosești a / cmmdc * b.

Cel mai mare divizor comun se calculează cu algoritmul lui Euclid. Ideea este că perechea (a, b) și perechea (b, a % b) au aceiași divizori comuni:

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

Răspunsul este a, după ce b a ajuns 0 (b e mereu zero la final). Algoritmul se termină în câteva zeci de pași chiar pentru numere de ordinul miliardelor.

Varianta prin scăderi repetate (if (a > b) a -= b; else b -= a; până când sunt egale) apare des la Subiectul I, pentru că se urmărește ușor pe hârtie, dar e mult mai lentă.

Cmmmc-ul nu are algoritm propriu: cmmmc = a / cmmdc(a, b) * b, cu împărțirea înaintea înmulțirii, ca să nu depășești tipul. Pentru mai multe numere, acumulezi: pornești cu d = 0 și faci d = cmmdc(d, x) pentru fiecare x.

Detaliile și tabelul pentru 84 și 36 sunt în lecția despre cmmdc.

Lecția care merge mai departe: Cel mai mare divizor comun