使用歐幾里德算法的最大公約數？

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

其實沒有必要計算更大數量Euclid算法自我管理。 這裏是工作代碼：

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