求两数的最大公约数和最小公倍数

发表于
本文字数： 370 阅读时长 ≈ 1 分钟

辗转相除法求两数最大公约数和最小公倍数的代码

突然想不起来给定两个数，然后让求最大公约数和最小公倍数，该怎么求了

于是去网上搜索，才想起来可以用辗转相除法求两个数的最大公约数，而求两个数的最小公倍数就是将这两个数相乘然后除以最大公约数，算法实现代码如下

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // 求两数的最大公约数
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 求两数的最小公倍数
    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
}