Algoritmul lui Euclid - CMMDC în C++

Ce este CMMDC?

Cel mai mare divizor comun (CMMDC) al două numere întregi este cel mai mare număr natural care divide ambele numere fără rest.

Algoritmul lui Euclid

Algoritmul lui Euclid se bazează pe observația că CMMDC(a, b) = CMMDC(b, a % b), unde a % b este restul împărțirii lui a la b.

Varianta Iterativă

Copiază
1#include <iostream>
2using namespace std;
3
4int cmmdc(int a, int b) {
5    while (b != 0) {
6        int r = a % b;
7        a = b;
8        b = r;
9    }
10    return a;
11}
12
13int main() {
14    int a, b;
15    cout << "Introduceti doua numere: ";
16    cin >> a >> b;
17    cout << "CMMDC(" << a << ", " << b << ") = " << cmmdc(a, b) << endl;
18    return 0;
19}

Varianta Recursivă

Copiază
1int cmmdc_recursiv(int a, int b) {
2    if (b == 0)
3        return a;
4    return cmmdc_recursiv(b, a % b);
5}

CMMMC (Cel Mai Mic Multiplu Comun)

Formula: CMMMC(a, b) = (a * b) / CMMDC(a, b)

Copiază
1int cmmmc(int a, int b) {
2    return (a / cmmdc(a, b)) * b; // Evităm overflow
3}

Complexitate

• •Timp: O(log(min(a, b)))
• •Spațiu: O(1) iterativ, O(log(min(a, b))) recursiv

Aplicații Practice

1. •Simplificarea fracțiilor
2. •Criptografie (RSA)
3. •Probleme de matematică discretă