最大公约数

说明：

计算最大公约数,这里只展示通过递归实现。

其方法使用的是数学上的==辗转相除法==

gcd相关的概念还有裴蜀定理 ，即任意两个数的组合必定是他们gcd的倍数。同样可以推广到更多数：如果这些数的gcd是d，那么他们的组合是d的倍数，如果d不是1，那么必然有无限个数无法被组合出来。

Java代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.math.BigInteger;

/**
 * @description: 求最大公约数
 * @author 长白崎
 * @date 2023/3/30 12:33
 * @version 1.0
 */
public class GCD {

    public static void main(String[] args) {
        //测试集
        System.out.println(gcd(24,60));
        System.out.println(gcdFun(24,60));
    }


    /**
     * 计算最大公约数方式1
     * @param a 数字1
     * @param b 数字2
     * @return 返回最大公约数
     */
    public static  int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }

    /**
     * Java特有的一种最大公约数计算方式
     * @param a 数字1
     * @param b 数字2
     * @return 返回最大公约数
     */
    public static  int gcdFun(int a,int b){
        BigInteger a1 = BigInteger.valueOf(a);
        BigInteger a2 = BigInteger.valueOf(b);
        return  Integer.parseInt(a1.gcd(a2).toString());
    }
}

C++代码模板：

1
2
3
int gcd(int a,int b){
    return b?a:gcd(b,a%b);
}