Algoritm pentru determinarea celui mai mare divizor comun a 2 numere (Metoda a II-a, Algoritmul lui Euclid)

Se citesc  de la tastatură 2 numere naturale. Să se determine folosind algoritmul lui Euclid și să se afișeze cel mai mare divizor comun al celor 2 numere

Exemplu: pentru numerele 2 și 8 se va afișa 2, pentru numerele 100 și 600 se va afișa 100, iar pentru numerele 2 și 9 se va afișa 1.

Se aplică algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a două numere. Se citesc numerele, iar variabilei r i se atribuie restul împărțirii lui a la b (a%b).  Cât timp restul este 0, adică b nu este un divizor a lui a, se execută instrucțiunea while, fiind conținutul algoritmului lui Euclid.

Vezi și: Algoritm pentru determinarea celui mai mare divizor comun a 2 numere (Metoda I – scăderi repetate)

#include<iostream>
using namespace std;
int main()
{
    int a,b,r;
    cout<<"a?"; cin>>a;
    cout<<"b?"; cin>>b;
    r=a%b;
    while (r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    cout<<b;
    return 0;
}

De asemenea, ai putea dori...

Lasă un răspuns

Acest sit folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.