最大公约数的算法.docVIP

. 1、查找约数法．先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数． 例如，求12和30的最大公约数．12的约数有：1、2、3、4、6、12；30的约数有：1、2、3、5、6、10、15、30．12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数．《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 　　翻译成现代语言如下： 　　第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 　　第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 　　则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 　　其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。　　、辗转相除法． 　　当两个数都较大时，采用辗转相除法比较方便．其方法是： 　　以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数． 　　例如：求4453和5767的最大公约数时，可作如下除法． 　　5767÷4453＝1余1314 　　4453÷1314＝3余511 　　1314÷511＝2余292 　　511÷292＝1余219 　　292÷219＝1余73 　　219÷73＝3 　　于是得知，5767和4453的最大公约数是73． 　　辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数． 、求差判定法． 　　如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两个数的最大公约数．例如：求78和60的最大公约数．78－60＝18，18和60的最大公约数是6，所以78和60的最大公约数是6． 　　如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公约数就是原来两数的最大公约数．例如：求92和16的最大公约数．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公约数是4，所以92和16的最大公约数就是4． 　　、分解因式法． 　　先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公约数． 　　例如：求125和300的最大公约数．因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公约数是5×5＝25． 　　 　　、短除法． 　　为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数的乘积． 　　例如：求180和324的最大公约数． 　　因为： 5和9互质，所以180和324的最大公约数是4×9＝36． 　　、除法法． 　　当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公约数． 　　例如：求19和152，13和273的最大公约数．因为152÷19＝8，273÷13＝21．（19和13都是质数．）所以19和152的最大公约数是19，13和273的最大公约数是13． 　　、缩倍法． 　　如果两个数没有之间没有倍数关系，可以把较小的数依次除以2、3、4……直到求得的商是较大数的约数为止，这时的商就是两个数的最大公约数．例如：求30和24的最大公约数．24÷4＝6，6是30的约数，所以30和24的最大公约数是6．