輾轉相除法， 又名歐幾里德算法（Euclidean algorithm）乃求兩個正整數(shù)之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。

來自 百度百科 的介紹，下面就不多廢話了

上代碼：

int BigestFactor(int m,int n)
{
    int r=m;
    while(r!=0)
    {
            r=m%n;
            m=n;
            n=r;         
    }
    return m;
}

代碼思路詳見這張流程圖：

輾轉相除法流程圖

所以來編個程序吧~
分數(shù)約分程序：

#include <iostream>

using namespace std;

int BigestFactor(int ,int);

int main()
{
    int m,n=0;   
    cin>>m>>n;
    int bf = BigestFactor(m,n);
    cout<<bf<<endl;
    cout<<m*1.0/bf<<endl<<n*1.0/bf<<endl;
    cin.get();
    cin.get();
    return 0;
}

int BigestFactor(int m,int n)
{
    int r=m;
    while(r!=0)
    {
            r=m%n;
            m=n;
            n=r;         
    }
    return m;
}

不解釋了，自己領悟

最后再紀念一下在公元前300年前發(fā)明輾轉相除法的歐幾里得

歐幾里得