辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。
来自 百度百科 的介绍，下面就不多废话了
上代码：
int BigestFactor(int m,int n)
{
int r=m;
while(r!=0)
{
r=m%n;
m=n;
n=r;
}
return m;
}
代码思路详见这张流程图：
辗转相除法流程图
所以来编个程序吧~
分数约分程序：
#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年前发明辗转相除法的欧几里得
欧几里得
