最大公因數(GCD)

最大公因數（Greatest Common Divisor，簡寫為G.C.D.；或Highest Common Factor，簡寫為H.C.F.）
這是很多程式的入門練習題，尤其是使用遞迴呼叫(recursive call)的方式。

如何找出兩個數的最大公因數呢?
最常見的方式是輾轉相除法---輾轉相除法，又名歐幾里得演算法(Euclidean algorithm)乃求兩個正整數之最大公因數的演算法。
這是已知最古老的演算法, 其可追溯至前300年。首次出現於歐幾里得的《幾何原本》(第VII卷，命題i和ii)中，而在中國則可以追溯至東漢出現的《九章算術》。這演算法並不需要把二數作質因數分解。

以下分別以C++實作這兩個方法:

《九章算術》
計算最大公因數
請輸入兩個數字:
1st: 96
2nd: 72
96>72, 96-72=24
24<72, 72-24=48
24<48, 48-24=24
24=24, 最大公因數為:24
請按任意鍵繼續 . . .

#include <iostream>
using namespace std;
int fun(int a, int b)
{
    if(a>b)
 {
  cout << a << ">" << b << ", " << a << "-" << b << "=" << a-b << endl;
  return fun(a-b,b);
 }
 else if(a<b)
 {
  cout << a << "<" << b << ", " << b << "-" << a << "=" << b-a << endl;
  return fun(a,b-a);
 }
 else
 {
  cout << a << "=" << b << ", ";
  return (a);
 }
}
int main(){
    int x,y;
    cout << "計算最大公因數\n" << "請輸入兩個數字:\n";
    cout << "1st: ";
    cin >>  x;
    cout << "2nd: ";
    cin >>  y;
    cout << "最大公因數為:" << fun(x,y) << endl;
    system("Pause");
    return 0;
}

《幾何原本》
計算最大公因數
請輸入兩個數字:
1st: 96
2nd: 72
96>72, 96%72=24
72%24=0, 最大公因數為:24
請按任意鍵繼續 . . .

#include<iostream>
using namespace std;
int fun(int a, int b){
    if(a%b){
  cout<<a<<">"<<b<<", "<<a<<"%"<<b<<"="<<a%b<<endl;
  return fun(b, a%b);
 }
 else{
  cout<<a<<"%"<<b<<"=0, ";
  return (b);
 }
}
int main(){
    int x,y;
    cout<<"計算最大公因數\n"<<"請輸入兩個數字:\n";
    cout<<"1st: ";
    cin>>x;
    cout<<"2nd: ";
    cin>>y;
 if(x>y)
  cout<<"最大公因數為:"<<fun(x,y)<<endl;
 else if(x<y)
  cout<<"最大公因數為:"<<fun(y,x)<<endl;
 else
  cout<<"最大公因數為:"<<x<<endl;
    system("Pause");
    return 0;
}