求最大公约数和最小公倍数---辗转相除法(欧几里得算法)

太过爱你忘了你带给我的痛 2024-03-25 13:56 45阅读 0赞

**目录**

一.GCD和LCM

1.最大公约数

2.最小公倍数

二.暴力求解

1.最大公约数

2.最小公倍数

三.辗转相除法

1.最大公约数

2.最小公倍数

--------------------

## 一.GCD和LCM ##

### 1.最大公约数 ###

**最大公约数**（Greatest Common Divisor，简称GCD）指的是两个或多个整数共有的约数中最大的一个数。例如，整数12和30的约数有1、2、3、6，但其中最大的约数是6，因此12和30的最大公约数是6。

最大公约数在数学中有着广泛的应用，例如可以用于简化分数、判断两个数是否互质、求解线性方程等。

特殊的gcd(0,n)为n,n为任意数

### **2.最小公倍数** ###

**最小公倍数**（Least common multiple , 简称LCM）是两个或多个整数中最小的能够被这些整数整除的正整数。换句话说，最小公倍数是这些整数的公共倍数中最小的一个。

例如，整数 6 和 8 的公共倍数包括 24、48、72 等，其中 24 是最小的一个，因此它们的最小公倍数是 24。

最小公倍数在数学和计算中经常使用，例如在分数的约分和通分、整数的约数分解、最简分式的求解等方面。

无法求0和一个数的最小公倍数

最小公倍数(LCM)=num1\*num2/最大公倍数(GCD)

## 二.暴力求解 ##

### 1.最大公约数 ###

思路:考虑特殊情况,当num1和num2一个为0,返回另一个的值.

两个数的最大公约数,一定不可能在(min(num1,num2),max(num1,num2)\]之间因为两者之中较小者的最大约数为本身,所以我们选择从较小者开始遍历,当都可以整除(也就是求余等于0)的时候,说明找到了最大公约数.

public static int gcd(int num1, int num2) {
            if(num1==0)
                return num2;
            if(num2==0)
                return num1;
            int min = num1 < num2 ? num1 : num2;
            for (; min >= 1; --min) {
                if (num1 % min == 0 && num2 % min == 0) {
                    return min;
                }
    
            }
            return min;
    
        }

### 2.最小公倍数 ###

思路:

两个数的最小公倍数,一定不可能在\[0,max(num1,num2))之间因为两者之中较大者的最大倍数为本身,所以我们选择从较大者开始遍历,当都可以被整除(也就是求余等于0)的时候,说明找到了最小公倍数.

public static int lcm(int num1, int num2) {
            int max = num1 > num2 ? num1 : num2;
            for (; max <= num1 * num2; ++max) {
                if (max%num1==0&&max%num2==0) {
                    return max;
                }
    
            }
            return max;
    
        }

## 三.辗转相除法 ##

**辗转相除法**，又称**欧几里得算法或辗转相减法**，是一种求最大公约数（Greatest Common Divisor，简称GCD）的算法。

假设要求两个正整数a和b的最大公约数，辗转相除法的步骤如下：

1.  用a除以b，得到余数r；
2.  如果r等于0，那么b就是最大公约数；
3.  如果r不等于0，那么用b除以r，得到余数r1；
4.  如果r1等于0，那么r就是最大公约数；
5.  如果r1不等于0，那么继续用r除以r1，得到余数r2，以此类推，直到余数为0为止。

举个例子，假设要求36和24的最大公约数，辗转相除法的步骤如下：

36 ÷ 24 = 1 ... 12

24 ÷ 12 = 2 ... 0

因此，36和24的最大公约数是12。

辗转相除法的时间复杂度为O(logn)，其中n为a和b中较大的那个数的位数。因此，辗转相除法是一种高效的求最大公约数的方法，被广泛应用于计算机科学和数学领域。

### 1.最大公约数 ###

**1.递归方法求解**

//递归求解
        public static int gcd(int num1, int num2) {
            if (num2 == 0)
                return num1;
            return gcd(num2, num1 % num2);
    
        }

**2.迭代方法求解**

//迭代求解
        public static int gcd(int num1, int num2) {
            int c = num1 % num2;
            while (c != 0) {
                num1 = num2;
                num2 = c;
                c = num1 % num2;
            }
            return num2;
    
    
        }

### 2.最小公倍数 ###

**最小公倍数(LCM)=num1\*num2/最大公倍数(GCD)**

public static int lcm(int num1, int num2) {
            int x = num1, y = num2;
            int c = num1 % num2;
            while (c != 0) {
                num1 = num2;
                num2 = c;
                c = num1 % num2;
            }
            return x / num2* y ;  //相当于x*y/num2,但是先除后乘可以避免溢出
    
    
        }