輾轉(zhuǎn)相除法先较， 又名歐幾里德算法（Euclidean algorithm）乃求兩個(gè)正整數(shù)之最大公因子的算法。它是已知最古老的算法悼粮， 其可追溯至公元前300年前闲勺。
來自 百度百科 的介紹，下面就不多廢話了
上代碼：
int BigestFactor(int m,int n)
{
int r=m;
while(r!=0)
{
r=m%n;
m=n;
n=r;
}
return m;
}
代碼思路詳見這張流程圖：
輾轉(zhuǎn)相除法流程圖
所以來編個(gè)程序吧~
分?jǐn)?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;
}
不解釋了扣猫，自己領(lǐng)悟
最后再紀(jì)念一下在公元前300年前發(fā)明輾轉(zhuǎn)相除法的歐幾里得
歐幾里得
