最大公约数的算法.doc

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