数据结构与算法学习(三)——最大公约数和最小公倍数

最大公约数和最小公倍数是我们小学学习的，那时候我们求最大公约数，往往是将两数的所有约数全部列出来，然后找出共有的约数中其中最大的那个；而求最小公倍数也往往是将两数的倍数一一列出，找出相等的倍数中最小的那个。

好吧😂，原谅我的无知。。。原来还可以用短除法求最大公约数和最小公倍数，小学白学了😂，一直穷举穷举了六年，我枯了😭。

短除法
最大公约数：

最小公倍数：

使用计算机编程计算最小公约数和最小公倍数有很多种方法，下面将进行总结。

1. 最大公约数

求最大公约数的方法我总结了4种方法：

1. 穷举法
2. 辗转相除法
3. 更相减损术
4. 算法

下面分别讲解：

1.1 穷举法

• 分析：穷举法是最笨，但是最容易想到的方法😀。根据定义，我们只需找出一个数能同时被两个数整除，且为此类数中最大的一个即可。取两个数中较小的数，从这个数开始递减，直到能同时被两个数整除，则此时，可求得最大公约数。

• 代码实现

  public static int maxNum(int numA, int numB) {
    int i;
    for(i = numA > numB ? numB : numA; i > 0; i--) {
        if((numA % i == 0) && (numB % i == 0)) {
            break;
        }
    }
    return i;
  }
  

1.2 辗转相除法(欧几里得算法)

辗转相除法，又名欧几里得算法，其基本原理： 两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数 。一看这基本原理是不是激动了一下😎，又可以用递归了。下面给出递归和非递归的两种实现。具体介绍详见维基百科

维基百科错误

(这怕是假的维基百科，还真像《瑞克和莫蒂》中说的一样，谁都可以写。。。确实谁都可以写23333😂。辗转相除法和更相减损术傻傻分不清🙄，我已提交错误)。

1.2.1 非递归实现

• 分析：取这两个数，将大数放在numA中，小数放在numB中，求numA除以numB的余数，放在temp中，根据辗转相除法(欧几里得算法)，两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。如果余数temp不为 ，一直循环将numB值赋给numA，temp值赋给numB，再对numA和numB求余，直到余数temp为 ，则此时numB为最大公约数。

• 代码实现

  public static int gcd(int numA, int numB) {
  
      //如果数B比数A大，交换A和B的值，保证A中存放大数，B中存放小数
      //A和B值的大小并不影响取余的结果
      //if(numB > numA) {
      //  numA = numA ^ numB;
      //  numB = numA ^ numB;
      //  numA = numA ^ numB;
      //}
      
      int temp = numA % numB;
      while(temp != 0) {
          numA = numB;
          numB = temp;
          temp = numA % numB;
  }
        
      return numB;
  }
  

1.2.2 递归实现

• 代码实现

  public static int gcd(int numA, int numB) {
    
    /*如果数B比数A大，交换A和B的值，保证A中存放大数，B中存放小数*/
    if(numB > numA) {
        numA = numA ^ numB;
        numB = numA ^ numB;
        numA = numA ^ numB;
    }
    
    int temp = numA % numB;
    if(temp != 0) {
        numB = gcd(numB, temp);
    }
    return numB;
  }
  

1.3 更相减损术

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。——《九章算术》

白话译文：（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。——《百度百科》

先搬出原著古文以及百度百科(时没有看见维基百科的，看来要找个时间给它安排上😎)的译文，不得不佩服古人的智慧。更相减损术的基本步骤是：对于这两个数a,b，首先判断他们是否为偶数，如果是偶数，两者都除以2；如果不是，则用较大的数a减去较小的数b，用得到的差temp与较小的数b进行比较，如果相等，则差temp即为最大公约数；如果不相等，令将小数b的值赋给大数a，差temp的值赋给小数b，即a = b，b = temp。继续从头开始执行，直到相等时，temp值乘以约去的2即为最大公约数。(流程图待补充)

• 代码实现

  /*
   * 更相减损术中对2进行约分知识为了简化运算，不影响最后的结果，所以代码省去了对二的约分。
   */
  public static int gcd(int numA, int numB) {   
    while(numA != numB) {
        if(numA > numB) {
            numA -= numB;
        }else {
            numB -= numA;
        }
    }
    return numA;
  }
  

1.4 算法

---

2. 最小公倍数

求最大公约数的方法我总结了2种方法：

1. 穷举法
2. 利用最大公约数

2.1 穷举法

• 分析：同样的最笨也最容易想到的方法，根据最小公倍数的定义，只要找出两个数公倍数中最小的那个即可。

• 代码实现

  public static int lcm(int numA, int numB) {
    if(numB > numA) {
        numA = numA ^ numB;
        numB = numA ^ numB;
        numA = numA ^ numB;
    }
    while(numA % numB != 0) {
        numA += numA;
    }
    return numA;
  }
  

2.2 利用最大公约数

• 分析：由于最大公约数和最小公倍数存在性质，两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。设这两个数分别为 , ，最大公约数为 ,最小公倍数为 ，则有 ，由此可得 ，考虑到可能会超出数值范围，将上述公式改写为 。

• 代码实现(注意其中gcd()方法需要实现，方法见上文)

  public static int lcm(int numA, int numB) {
    return numA / gcd(numA, numB) * numB;   //gcd()方法求最大公约数
  }
  

3. 参考文章

1. https://blog.csdn.net/Holmofy/article/details/76401074