Cel mai mare divizor comun

Un număr întreg $d$ se numește cel mai mare divizor comun a numerelor întregi $a$ și $b$ dacă și numai dacă pentru orice divizor comun $c$ al lui $a$ și $b$, $d$ este un divizor al lui $c$.

În cazul în care impunem condiția $d>0$ este relativ simplu de verificat dacă $d$ este unic. Acest număr se notează cu $c.m.m.d.c(a,b)$, sau mai simplu: $(a,b)$.

Folosind principiul bunei ordonări a numerelor naturale, putem deduce că $c.m.m.d.c(a,b)$ este cel mai mic număr pozitiv care poate fi scris ca o combinație liniară a lui $a$ și $b$, adică cel mai mic număr natural de forma $a*x+b*y$, unde $x,y$ sunt numere întregi.

C.M.M.D.C reprezinta numarul maxim provenit din intersectarea multimilor divizorilor celor doua numere. Unul din algoritmii de generare a c.m.m.d.c (dar care nu este foarte eficient) este:

(a,b numere naturale nenule)

CAT TIMP (a!=b)
{
    DACĂ (a>b)
    {
        a = a - b;
    }
    ALTFEL
    {
        b = b - a;
    }
}
cmmdc=a;

sau

(a,b numere naturale nenule)
        
executa{
        rest=a%b;
        a=b;
        b=rest;
        }cat timp(rest<>0);
cmmdc=a;

Programul in C++ pentru aflarea CMMDC a n numere este:

#include <iostream>
using namespace std;
 
int cmmdc(int a, int b) {
  while (a != b) {
    if (a > b)
      a -= b;
    else 
      b -= a;
  }
  return a;
}
 
int cmmdc2(int a, int b) {
  for (int r = a % b; r != 0; a = b, b = r, r = a % b)
    ;
  return b;
}
 
int main() {
  int n, *a, b;
  cout << "n=";
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; i++) {
    cout << "a[" << i << "]:";
    cin >> a[i];
  }
 
  for (int i = 1; i < n; i++)
    if(i == 1)
      b = cmmdc(a[i - 1], a[i]);
    else
      b = cmmdc(b, a[i]);
 
  cout << b;
}