Question

设计一种算法，求288和123的最大公约数．

Answer 1

答案：略
解析：

算法1：辗转相除法：用较大的数除以较小的数，将所得余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则较小的数就是两数的最大公约数． 288=123×2＋42； 123=42×2＋39； 42=39×1＋3； 39=3×13． ∴288和123的最大公约数是3． 算法2：更相减损术：以较大的数减去较小的数，接着把所得差与较小数比较，并以大数减小数，继续这个操作，直到所得数相等为止，则这个数就是两数的最大公约数． 288－123=165； 165－123=42； 123－42=81； 81－42=39； 42－39=3； 此处可以用39－3×13=0代替．