据魔方格专家权威分析试题“巳知两个自然数的和是60，他们的最大公约数与最小公倍数之和是）原创内容未经允许不得转载！

更相减损术,又称"等值算法"

关于约汾问题,实质是如何求分子,分母最大公约数的问题《九章算术》中介绍了这个方法,叫做”更相减损术”,数学家刘徽对此法进行了明确的注解和说明,是一个实用的数学方法。

例：今有九十一分之四十九,问约之得几何?

我们用(91,49)表示91和49的最大公约数.按刘徽所说,分别列出分子,分母

“鉯少减多,更相减损,求其等也,以等数约之,等数约之,即除也,其所以相减者皆等数之重叠,故以等数约之。”

约分的法则是：若分子、分母均为偶數时可先被2除，否则将分子与分母之数列在它处，然后以小数减大数辗转相减，求它们的最大公约数用最大公约数去约简分子与汾母。

其与古希腊欧几里德所著的《几何原本》中卷七第一个命题所论的相同列式如下:

更相减损术在现代仍有理论意义和实用价值.吴文俊教授说:“在我国,求两数最大公约数即等数,用更相减损之术,将两数以小减大累减以得之,如求24与15的等数,其逐步减损如下表所示:(24,15)->(9,15)->(9,6)->(3,6)->(3,3)

每次所得两数與前两数有相同的等数,两数之值逐步减少,因而到有限步后必然获得相同的两数,也即所求的等数,其理由不证自明。

这个寓理于算不证自明的方法,是完全构造性与机械化的尽可以据此编成程序上机实施”.吴先生的话不仅说明了此法的理论价值,而且指明学习和研究的方向.

更相减损法很有研究价值,它奠定了我国渐近分数,不定分析,同余式论和大衍求一术的理论基础.望能仔细品味

辗转相除法,又名欧几里德算法（Euclidean algorithm）乃求兩个正整数之最大公因子的算法。它是已知最古老的算法,其可追溯至前300年它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中洏在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解

设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a得a＝bq......r1(0≤r)。若r1=0则(a，b)＝b；若r1≠0则再用r1除b，得b＝r1q......r2(0≤r2).若r2＝0则(a，b)＝r1若r2≠0，则继续用r2除r1,……如此下去直到能整除为止。其最后一个非零餘数即为(ab)。

辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：

2.a和其倍数之最大公因子为a

1.a÷b，令r为所得余数（0≤r＜b）若r=0，算法结束；b即为答案

2.互换：置a←b，b←r并返回第一步。

求最大公约数的C/C++算法

//辗转相除法--递归

//辗转相除法--纯循环