作
者
● ●
宁波市鄞州区中河实验小学
505班 胡嘉颖
指导老师 徐佩云
求两个数最大公因数的方法,有列举法、分解质因数法、短除法等,那还有没有别的方法可以求两个数的最大公因数呢?
第一种缩小倍数法
先把这两个数中较小数的因数列举出来,然后再从这些因数中找出较大数的因数,找出来的就是这两个数的公因数,再从这些公因数里面找最大,就是这两个数的最大公因数了。但它不适用于计算较大的数的最大公因数。
例如:求8和12的最大公因数。
8的因数是:①、②、④、8; 8和12的公因数是:1、2、4;
8和12的最大公因数是:4。
第二种方法是求差判定法
如果两个数相差不大,可以用大数减去小数,所得的差与小数的最大公因数就是原来两个数的最大公因数。例如:求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。
还有两种稍微复杂,但应用的范围广,比较适合求较大数的公因数。
第三种辗转相除法,也叫欧几里德算法
两个数中用较大数除以较小数,以除数和余数反复做除法运算,最终当余数为0时,那么最后的除数就是两个数的最大公因数。算法举例:
求319和377的最大公因数。
377÷319=1……58 319÷58=5……29 58÷29=2……0
余数为0,除数29即为最大公因数。
第四种更相减损法
它出自《九章算术》。具体方法:第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
求98与63的最大公约数。
由于63不是偶数,把98和63以大数减小数,并辗转相减:
98-63=35 63-35=28 35-28=7
28-7=21 21-7=14 14-7=7
所以,98和63的最大公约数等于7。
数学知识奥秘无穷,需要我们用一颗不断进取和探索的心,去留心,去发现。
联系客服