前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最大公约数和最小公倍数

最大公约数和最小公倍数

作者头像
贪挽懒月
发布2021-02-04 10:26:47
1K0
发布2021-02-04 10:26:47
举报
文章被收录于专栏: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

代码实现:

代码语言:javascript
复制
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

代码实现:

代码语言:javascript
复制
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。所以,要求最小公倍数,可以先用上述方法求出最大公约数。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档