最大公约数的算法.doc

.1、,再从两个数的约数中找出公有的约数,,:1、2、3、4、6、12;30的约数有:1、2、3、5、6、10、15、:1、2、3、6,《九章算术》是中国古代的数学专著,其中的“更相减损术”能够用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”翻译成现代语言如下: 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。 3、辗转相除法. 当两个数都较大时,: 以小数除大数,如果能整除,;,直到一个除法能够整除,这时作为除数的数就是所求的最大公约数. 例如:求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. 辗转相除法适用比较广,比短除法要好得多,、求差判定法. 如果两个数相差不大,能够用大数减去小数,:-60=18,18和60的最大公约数是6,因此78和60的最大公约数是6. 如果两个数相差较大,能够用大数减去小数的若干倍,一直减到差比小数小为止,:-16=76,76-16=60,60-16=44,44-16=28,28-16=12,12和16的最大公约数是4,因此92和16的最大公约数就是4. 5、分解因式法. 先分别把两个数分解质因数,再找出它们全部公有的质因数,然后把这些公有质因数相乘,得到的积就是这两个数的最