更相减损术

更相减损术 什么是更相减损之术c语言更相减损术求最大公约数更相减损术

更相减损术《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来球两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。

以等数约之。

”翻译成现代语言如下：第一步：任意给顶两个正整数；判断他们是否都是偶数。

若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。

继续这个 *** 作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。

求“等数”的办法是“更相减损”法，实际上就是辗转相除法。

例用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并展转相减98-63=3563-35=2835-28=728-7=1414-7=7

更相减损术到底是怎样一回事