每日算法（10）——最大公约数和最小公倍数

1、两个整数的最大公约数和最小公倍数

（1）最大公约数参考百度

① 辗转相除法——用m除以n，然后用n代替m，余数remainder代替n，能够整除时m就是最大公约数
② 更相减损术——始终用较大的数减较小的数，直至差为零
③ 穷举法——先获得较小的数min，然后递减遍历，当能被m和n同时整除时的min就是最大公约数
④ 递归算法——用m除以n，然后用余数remainder和n继续递归运算，能整除时结束

（2）最小公倍数参考百度

由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）× [a，b] = a × b。所以，求两个数的最小公倍数，可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。

2、具体代码

package com.peter.algorithm.other;

import org.junit.Test;

public class GcdAndLcm {
    @Test
    public void test() {
        int m = 63;
        int n = 98;
        System.out.println(m + "和" + n + "的最大公约数为: " + getGreatestCommonDivisorByDivision(m, n));
        System.out.println(m + "和" + n + "的最大公约数为: " + getGreatestCommonDivisorBySubtraction(m, n));
        System.out.println(m + "和" + n + "的最大公约数为: " + getGreatestCommonDivisorByEnum(m, n));
        System.out.println(m + "和" + n + "的最大公约数为: " + getGreatestCommonDivisorByRecursion(m, n));
        System.out.println(m + "和" + n + "的最小公倍数为: " + getLeastCommonMultiple(m, n));
    }

    //辗转相除法
    public static int getGreatestCommonDivisorByDivision(int m, int n) {
        if ( m * n == 0 ) {
            throw new IllegalArgumentException("The parameter contains zero.");
        }
        while (n != 0 ) {
            int remainder = m % n;
            m = n;
            n = remainder;
        }
        return m;
    }

    //更相减损术
    public static int getGreatestCommonDivisorBySubtraction(int m, int n) {
        if ( m * n == 0 ) {
            throw new IllegalArgumentException("The parameter contains zero.");
        }
        while (m != n) {
            if (m > n) {
                m = m - n;
            } else {
                n = n - m;
            }
        }
        return m;
    }

    //穷举法
    public static int getGreatestCommonDivisorByEnum(int m, int n) {
        if ( m * n == 0 ) {
            throw new IllegalArgumentException("The parameter contains zero.");
        }
        int i = (m < n) ? m : n;
        for (;i > 0; i--) {
            if (m % i == 0 && n % i == 0) {
                break;
            }
        }
        return i;
    }

    //递归算法
    public static int getGreatestCommonDivisorByRecursion(int m, int n) {
        if ( m * n == 0 ) {
            throw new IllegalArgumentException("The parameter contains zero.");
        }
        if (m % n == 0) {
            return n;
        }
        return getGreatestCommonDivisorByRecursion(n, m % n);
    }

    //两个整数的最小公倍数等于这两个数的乘积除以其最大公约数
    public static int getLeastCommonMultiple(int m, int n) {
        if ( m * n == 0 ) {
            throw new IllegalArgumentException("The parameter contains zero.");
        }
        return m * n / getGreatestCommonDivisorByRecursion(m, n);
    }
}

3、测试结果

整数	最大公约数	最小公倍数
63与98	7	882
24与60	12	120
62与124	2	4154