Cel mai mare divizor comun

#include <iostream>

using namespace std;

int main()
{
   int a, b;
   cin>>a; //primul numar
   cin>>b; //al doilea numar
   while(a!=b)
   {
      if(a>b)
         a=a-b;
      else
         b=b-a;
   }
   //cel mai mare divizor va fi unul dintre cele doua numere intrucat la final acestea devin egale
   cout<<a;
}

Explicatie:

- citim cele 2 numere: a si b
- cat timp cele 2 numere nu sunt egale vom scadea din cel mai mare dintre ele pe cel mai mic
- la final cele doua numere vor deveni egale, iar acest numar reprezinta cmmdc-ul

ATENTIE!

In cazul in care unul dintre cele doua numere este 0 algoritmul nostru nu ne va ajuta, intrand in ciclu infinit

Metoda prin impartiri repetate

#include <iostream>

using namespace std;

int main()
{
   int a, b;
   cin>>a; //primul numar
   cin>>b; //al doilea numar
   while(b!=0)
   {
      int r=a%b;
      a=b;
      b=r;
   }
   //cel mai mare divizor comun va fi memorat de variabila a
   cout<<a;
}

Explicatie:

- citim cele 2 numere: a si b
- aceasta metoda se bazeaza pe impartirea deimpartitului(a) la impartitor(b) si memorarea restului(r), pana cand acest rest devine 0
- impartitorul devine deimpartit, iar restul devine impartitor
- in momentul cand restul impartirii devine 0, cmmdc-ul va fi stocat in a

OBSERVATIE!

Acest algoritm functioneaza si in cazul in care unul dintre cele doua numere este 0(daca ambele sunt 0, algoritmul va afisa 0, ceea ce nu are sens), iar in plus acest algoritm este mai eficient