2017北京公务员行测备考：“消减法”求最大公约数和最小公倍数

公务员考试网

求几个数的最小公倍数和最大公约数，除了我们比较熟悉的短除法和分解质因数法之外，还有《几何原本》中记载的“辗转相除法”，这种算法在我国则要追溯到《九章算术》中记载的“更相减损术”。经过分析分解质因数法(短除法原理相同)和更相减损术(辗转相除法原理相同)的原理，总结以上两种方法的特点及优缺点，可以总结出一种求“最小公倍数”和“最大公约数”的新方法——“消减法”。
    一、“消减法”介绍
    任何两个不相等的数，它们的和或差里一定含有这两个数的公约数，为了方便，这里就采用两个数的差与其中一个数相互约分的方式，消去这两个数的公约数，从而求得最大公约数和最小公倍数。
    “消减法”具体求法是这样的：用其中一个数作分子，这两个数的差作分母，再把它化成最简分数。把最简分数的分子与另一个数(不是原来作分子的那个数)相乘，所得的乘积就是这两个数的最小公倍数;拿原分母(原来两个数的差)除以最简分数的分母，得到的商就是这两个数的最大公约数。
    比如：求18和30的最小公倍数和最大公约数。
    18/(30-18)=3/2
    则，最小公倍数为3*30=90;
    “消减法”同样也适用于求三个数的最小公倍数和最大公约数，方法如下：
    (1)求最小公倍数：
    ①用第一个数作分子，前两个数的差作分母，化成最简分数;
    ②用①中最简分数的分子与第二个数相乘的积作分子，用这个乘积与第三个数的差作分母，化成最简分数;
    ③用②中的最简分数的分子与第三个数相乘的积就是这三个数的最小公倍数。
    (2)求最大公约数：
    ①用第一个数作分子，前两个数的差作分母，化成最简分数;
    ②用前两个数的差除以①中最简分数的分母所得的商作分子，用这个商与第三个数的差作分母，化成最简分数;
    ③用②中原分母除以②中最简分数的分母所得的商就是这三个数的最大公约数。
    例：求18、12、15的最小公倍数和最大公约数。
    (1)求最小公倍数
    ①18/(18-12)=3/1;
    ②3*12=36,36/(36-15)=12/7;
    ③12*15=180;
    180即为12、15、18的最小公倍数。
    (2)求最大公约数
    ①18/(18-12)=3/1;
    ②6÷1=6,6/(15-6)=2/3;
    ③9÷3=3;
    3即为12、15、18的最大公约数。
    二、原理分析
    任意两个正整数A>B ，不妨令它们最大公约数为m，A和B可表示为：
    A=m*a，B=m*b
    A/(A-B)=m*a/(m*a-m*b)=a/(a-b) (B作分子同理)
    易知A和B的最小公倍数为m*a*b=a*B，最大公约数m=(A-B)/(a-b)。