Самый большой общий делитель с использованием евклидова алгоритма?

Question

Так что у меня проблема с моим кодом здесь.

Я кодирую самый большой общий делитель, используя алгоритм Евклида, и я не могу использовать цикл, чтобы сохранить разделение, чтобы он повторялся до тех пор, пока я не получу наибольший общий делитель. Так что пока я могу получить остаток, но не знаю, как идти дальше оттуда в основном.

Любая помощь будет принята с благодарностью!

Вот то, что я до сих пор

#include <iostream> 
#include <string> 
#include <cmath> 

using namespace std; 

int a;//Holds the first number 
int b;//Holds the second number 
int temp;//Assign to greatest number 
int hold;//Assign to smaller number 
float euclid;//soon to be function? 
int leftover; 
float gcd; 



int main() 
{ 
    cout<<"Welcome to Brian Garnadi's Version of GCD!\n"<<endl; 
    cout<<"Enter the first integer to be calculated: "; 
    cin>> a; 
    cout<<"Now enter the second integer: "; 
    cin>>b; 

    if (a>b)//Determines bigger number 
    {temp=a; 
     hold=b; 
    } 
    if (a<b)//Determines smaller number 
    { 
     temp=b; 
     hold=a; 
    } 

    leftover= temp%hold; 

    cout<<"\nThe remainder of the two numbers divided is "<<leftover<<".\n"<<endl; 

} 

Answer 1

На самом деле нет необходимости вычислять большее число алгоритм Евклида управляет сам. Вот рабочий код:

#include <iostream> 
using namespace std; 
int gcd(int m,int n) 
{ 
    if(n == 0) 
     return m; 
    return gcd(n, m % n); 
} 

int main() 
{ 
    int a,b,answer; 
    cout<<"Welcome to Brian Garnadi's Version of GCD!\n"<<endl; 
    cout<<"Enter the first integer to be calculated: "; 
    cin>> a; 
    cout<<"Now enter the second integer: "; 
    cin>>b; 
    answer = gcd(a,b); 
    cout << "The GCD of the two numbers is : " << answer << endl; 
    return 0; 
} 

Answer 2

Не забывайте обрабатывать отрицательные числа в алгоритме.

gcd(m, n) = gcd(n, m%n) when n != 0 
      = m    when n = 0 

функция:

int gcd(int m, int n) { 
    if(m == 0 && n == 0) 
     return -1; 

    if(m < 0) m = -m; 
    if(n < 0) n = -n; 

    int r; 
    while(n) { 
     r = m % n; 
     m = n; 
     n = r; 
    } 
    return m; 
}