求解非负数的：最大公约数 最小公倍数

最近在做题的时候遇到了需要 求两个非负数的最小公倍数，想了半天，感觉哪种方法效率都满低的，然后搜索了一下：哦吼！果然还是 前辈厉害-- 欧几里得算法(又名：辗转相除 法)

ok ,看看百度咋说：

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

扩展欧几里得算法可用于RSA加密等领域。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 ÷ 615 = 3 (余 152)

615 ÷ 152 = 4(余7)

152 ÷ 7 = 21(余5)

7 ÷ 5 = 1 (余2)

5 ÷ 2 = 2 (余1)

2 ÷ 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

 懂了吧！

就是不断的让 除数/余数，啥时候余数=0，啥时候就停了，这个时候的除数就是两个数的最大公约数

最大公约数 (默认a>b)

最大公约数--Java 代码如下(a>b)(容易理解，但是有点繁冗--小白理解推荐)：

public class Main {public static void main(String[] args){System.out.println(gcd(24,768));}// a>bpublic  static int gcd(int a, int b) {if (a % b == 0) {return b;}int temp = a % b;a = b;b = temp;return gcd(a, b);}}// output : 24 

最大公约数-- Java代码(a>b)(简化代码，深入理解)：

    //a>bpublic static int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}

最小公倍数

那就好求了嘛：M*N = 最大公约数*最小公倍数，那么：

    public int lcm(int a, int b) {int temp = a * b;int gcdNum = gcd(a, b);return temp / gcdNum;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！