题解 | #求最小公倍数#

• 最小公倍数，两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

• 求解方法：

  1. 分解质因数法：最小公倍数 = 数的所有的质因数的乘积（共有的因数只取一次）
  2. 公式法：两个数的乘积 = 两个数的最大公约数与最小公倍数的积

• 切入点：找出两数的所有因数

• 情景：无公因数，则最小公倍数为两数乘积；一个数为另一个数因数，则最小公倍数为另一个大的数；存在公因数，确定最大公因数，求解最小公倍数。

综合情景考虑，建立一个长度为较小的数的数组，下标index+1表示因数的值，值表示是否为因数（为节省内存空间，将两个数的因数放在同一个数组中，值为1表示为一个数的因数，值为2表示为两个数的因数，即公因数）。计算获得所有的因数，找出最大公因数（数组倒序循环，第一个值为2的即为最大公因数），从而计算最小公倍数 = m * n / (index+1)，因为都是整数，所以也不用考虑小数的问题。

代码实现：

public static int getCM(int m, int n) {

        //需要的最短长度公因数数组长度
        int max = m;
        if (m > n) {
            max = n;
        }
        // 用于标识公因数
        int[] sons = new int[max];

        // 从1开始计算因数
        for (int i = 1; i <= max; i++) {
            if (m % i == 0) {
              // i 为 m 因数
                sons[i - 1] += 1;
            }
            
            if (n % i == 0) {
              // i 为 n 因数
                sons[i - 1] += 1;
            }
        }

        for (int i = max; i > 0; i--) {
          // 当数组值为2时，该数组下标i+1为公因数，从最后一个开始，获取最大公因数
            if (sons[i - 1] == 2) {
                return  m * n / i;
            }
        }
  
        // 最差情况为，两数无公因数，最小公倍数为 m*n
        return m * n;
    }