Cel mai mare divizor comun

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

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;
}