Java 实现最大公约数与最小公倍数

给定整数 a 和 b，如何求两个数的最大公约数与最小公倍数？

最大公约数

首先说明一下因数，因数是指一个数可以整除的数，如 6 的因数有 1、 2、3 和 6，12 的因数有 1、2、3、4、6 和 12

最大公约数即为两个数共有的因数中最大的那个数，比如 6 和 12 的共有因数有 2、3 和 6，那么最大公约数即为 6

若使用代码求最大公约数，有一个简单的方法就是倒序枚举小于两个数的最小值的所有数，直到枚举的数可以被两个数整数位置，但是显然这个方法效率过低。

这里给出快速计算最大公约数的方法

	/**
     * 计算最大公约数
     * @param a
     * @param b
     * 
     * @return 最大公约数
     */
    public int gcd(int a, int b) {
        // 如果 b 为 0，直接返回 a
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最小公倍数

倍数的定义这里就不聊了

最小公倍数是指两个数的共有倍数中最小的那个数，比如 6 的倍数有 6、12、18、24 等等，12 的倍数有 12、24、36、48 等等，那么 6 和 12 的最小公倍数就是 12

求最小公倍数也可以有暴力解法，就是枚举所有倍数，取最小的满足条件的

但是有了最大公约数的话，就可以快速求出最小公倍数，计算公式为：

• 最小公倍数 = a * b / gcd(a, b)，其中 gcd(a, b) 是指 a 与 b 的最大公约数
• 即最小公倍数为给定两个数的乘积除以这两个数的最大公约数

这里给出代码：

    /**
     * 求最小公倍数
     * @param a
     * @param b
     * @return
     */
    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
    
	/**
     * 计算最大公约数
     * @param a
     * @param b
     *
     * @return 最大公约数
     */
    public int gcd(int a, int b) {
        // 如果 b 为 0，直接返回 a
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

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