专栏首页JavaEE最大公约数和最小公倍数

最大公约数和最小公倍数

一、最大公约数

1. 是什么:

首先来回忆一下什么叫最大公约数:指两个或多个整数共有约数中最大的一个。比如60和24,60的约数有[1,2,3,4,5,6,10,12,15,20,30,60],24的约数有[1,2,3,4,6,8,12,24],他们共同的约数有[1,2,3,4,6,12],共同约数种最大的是12,所以最大公约数就是12。

2. 如何求最大公约数?

在数学中,我们用分解质因数和短除法来求解,如下图,就是百度经验上用短除法求最大公约数和最小公倍数的一个过程。

短除法

那么用程序如何实现呢?

其实如果要用程序实现短除法求解,可能不是那么简单。我们可以用另一种方法,叫做辗转相除法,又叫欧几里得算法

3. 欧几里得算法求最大公约数:

我们用(A, B)表示求A(较大的那个数)和B(较小的那个数)的最大公约数。欧几里得算法的公式如下:

  • 首先让A / B = C ~ D,如果余数D为0,那么B就是最大公约数;
  • 如果D不为0,那么就让除数和余数继续做上面的运算,即B / D = E ~ F,直到余数为0,此时的除数就是最大公约数。

欧几里得算法求(60, 24)的最大公约数步骤如下:

  • 60 / 24 = 2 ~ 12,所以(60, 24) = (24, 12)
  • 24 / 12 = 2 ~ 0,所以(60, 24) = (24, 12) = 12

代码实现:

public static int euclid(int a, int b){
        if (a == b){
            return a;
        }
        int dividend = Math.max(a, b); // 被除数
        int divisor = Math.min(a, b); // 除数
        int remainder = dividend % divisor; // 余数
        while (remainder != 0){
            dividend = divisor;
            divisor = remainder;
            remainder = dividend % divisor;
        }
        return divisor;
}

4. 更相减损术求最大公约数:

这是九章算术里面的求最大公约数的方法,我们用(A, B)表示求A(较大的那个数)和B(较小的那个数)的最大公约数,其步骤如下:

  • 首先判断A和B是否都是偶数,如果是,同时用2约分,要记住这一步约掉了几个2;
  • 当A和B不同时为偶数的时候,让A - B = C,当B和C相等时,C再乘以第一步约掉的2,约掉了几个就乘以几个,结果就是最大公约数;
  • 如果B和C不相等,那就看B和C谁更大,用更大的那个做被减数,更小的那个做减数,继续相减,直到减数和差相等。

更相减损术求(60, 24)的最大公约数步骤如下:

  • 60 / 2 / 2 = 15,24 / 2 / 2 = 6
  • 15 - 6 = 9
  • 9 - 6 = 3
  • 6 - 3 = 3

此时减数和差相等了,所以最大公约数就是3 * 2 * 2 = 12

代码实现:

public static int moreExclude(int a, int b){
        if (a == b){
            return a;
        }
        int minute = Math.max(a, b); // 被减数
        int minus = Math.min(a, b); // 减数
        int count = 0;
        while (minute % 2 == 0 && minus % 2 == 0){
            minute = minute / 2;
            minus = minus / 2;
            count ++;
        }
        int difference = minute - minus; // 差
        while (difference != minus){
            minute = Math.max(minus, difference);
            minus = Math.min(minus, difference);
            difference = minute - minus;
        }
        return (int) (Math.pow(2, count) * difference);
}

更相减损术代码看起来更复杂,多了一个while循环,实际上在数字不是很大的情况下,效率可能差不多,因为计算机做减法是比做除法更快的。但是当数字很大时,显然除法循环的次数更少,可以更快地得到结果。

二、最小公倍数

求出了最大公约数,求最小公倍数就很简单了,因为存在如下公式:

假如(a, b)的最大公约数是m,那么最小公倍数n = a * b / m。所以,要求最小公倍数,可以先用上述方法求出最大公约数。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最大公约数和最小公倍数

           辗转相除法(欧几里得算法)算是求最大公约数最简单高效的算法了,这几行代码用最简洁的方式写了这个算法,值得牢牢记住:

    刘开心_1266679
  • 【codevs1012】最大公约数和最小公倍数

    输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数

    饶文津
  • P1029 最大公约数和最小公倍数问题

    题目描述 输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数 条件: 1.P,Q是正整数 2.要...

    attack
  • 算法 | 求最大公约数和最小公倍数

    小学数学就学习了如何计算最大公约数(Greatest Common Factor,GCF)和最小公倍数(Lowest Common Multiple,LCM)。...

    fem178
  • C++中求两个正整数的最大公约数和最小公倍数

    最大公约数直接用辗转相除法,最小公倍数就是两个数的乘积除以最大公约数 #include<iostream> using namespace std; int g...

    用户1215536
  • 最大公约数和最小公倍数及其应用(Go语言解法)

    image.png 最大公约数(greatest common divisor)欧几里得辗转相除法:gcd(x,y)表示x和y的最大公约数进入运算时:x!=0,...

    李海彬
  • c语言:输入两个正整数 求最大公约数和最小公倍数

    其实学编程关键是学习其思想,如果你精通了一门,再去学其他的时候也很容易上手。C不会过时的,尤其是在unix、linux操作平台上,学好C是必须的。

    诸葛青云
  • 百度web前端面试题之求两个数的最大公约数和最小公倍数

    deepcc
  • java中请给出例子程序:找出两个数的最大公约数和最小公倍数

    d = n < m ? n : m; //get small number,得到小数

    马克java社区

扫码关注云+社区

领取腾讯云代金券