摘要：1．求最大公约数 (1)短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除.一直除到所得的商是两个互质数为止.然后把所有的除数连乘起来 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举.直到找到公约数立即中断列举.得到的公约数便是最大公约数 (3)辗转相除法 辗转相除法求两个数的最大公约数.其算法可以描述如下: ① 输入两个正整数m和n, ② 求余数r:计算m除以n.将所得余数存放到变量r中, ③更新被除数和余数:m=n.n=r, ④判断余数r是否为0.若余数为0.则输出结果,否则转向第②步继续循环执行 如此循环.直到得到结果为止. (4)更相减损术 我国早期也有解决求最大公约数问题的算法.就是更相减损术.在中记载了更相减损术求最大公约数的步骤:可半者半之.不可半者.副置分母•子之数.以少减多.更相减损.求其等也.以等数约之 步骤: Ⅰ．任意给出两个正数,判断它们是否都是偶数.若是.用2约简,若不是.执行第二步. Ⅱ．以较大的数减去较小的数.接着把较小的数与所得的差比较.并以大数减小数.继续这操作.直到所得的数相等为止.则这个数就是所求的最大公约数.

网址：http://m.1010jiajiao.com/timu3_id_4454068[举报]