【数论算法】最大公约数 & 最小公倍数

分手后的思念是犯贱 2023-10-07 23:28 62阅读 0赞

#### 目录 ####

*  1.概述
 *  2.代码实现
 *   *  2.1.最大公约数
     *  2.2.最小公倍数

## 1.概述 ##

（1）**最大公约数 (Greatest Common Divisor, GCD)**，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。a、b 的最大公约数记为 (a, b)，同样的，a、b 和 c 的最大公约数记为 (a, b, c)，多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法（也称欧几里得法）、更相减损法等。

（2）与最大公约数相对应的概念是**最小公倍数 (Least Common Multiple, LCM)**，两个或多个整数公有的倍数叫做它们的公倍数，其中除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数 a、b 的最小公倍数记为 \[a, b\]，同样的，a、b 和 c 的最小公倍数记为\[a, b, c\]，多个整数的最小公倍数也有同样的记号。

（3）关于最小公倍数与最大公约数，我们有这样的定理：(a, b) \* \[a, b\] = a \* b（a、b 均为整数)，即**整数 a、b 的最大公约数与最小公倍数之积等于 a 与 b 的积**。

## 2.代码实现 ##

下面分别来介绍求解整数 a 和 b 的最大公约数和最小公倍数代码实现。

### 2.1.最大公约数 ###

（1）辗转相除法/欧几里得算法的**递归代码实现**如下：

class Solution {
        
        //求整数 a 和 b 的最大公约数
        public int gcd(int a, int b) {
        
            if (b == 0) {
        
                return a;
            } else {
        
            	//定理运用：两个整数 a 和 b (b 不为 0) 的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数
                return gcd(b, a % b);
            }
        }
    }

（2）辗转相除法/欧几里得算法的**非递归代码实现**如下：

class Solution {
        
        //求整数 a 和 b 的最大公约数
        public int gcd(int a, int b) {
        
            int tmp = a;
            //保证 a >= b
            if (a < b) {
        
                a = b;
                b = tmp;
            }
            while (b > 0) {
        
                tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }
    
    	//另外一种写法
    	public int gcd2(int a, int b) {
        
            while (b != 0) {
        
                a %= b;
                a ^= b;
                b ^= a;
                a ^= b;
            }
            return a;
        }
    }

### 2.2.最小公倍数 ###

直接使用定理——(a, b) \* \[a, b\] = a \* b，即整数 a、b 的最大公约数与最小公倍数之积等于 a 与 b 的积。

class Solution {
          
        //求整数 a 和 b 的最小公倍数
        public int lcm(int a, int b) {
        
        	//定理运用：整数 a、b 的最大公约数与最小公倍数之积等于 a 与 b 的积
            return a / gcd(a, b) * b;
        }
    }