最大公因数=两数乘积/最大公倍数
于是两个问题变成了同一个问题，这边有三种方法：
1. 更相损减数
- 当两数相等，直接返回
- 否则，大数-小数，如果
差==小数，返回，否则重复这一过程- 出口情况是某一个数字等于1，则返回1
第一版
// 更相损减数实现
int maxCommonDivisor(int a, int b) {
while (a > 1 && b > 1) {
if (a == b) return a;
// 定a、b不相等且a>b
if (b > a) swap(a, b);
int temp = a - b;
a = b;
b = temp;
}
return 1;
}
但是其实没必要区分a、b究竟谁是大谁是小，或者说不必固定
这是更简洁的写法
// 更相损减数实现
int maxCommonDivisor(int a, int b) {
// 0，1的情况其实应该算是不合理的输入
// 说结果是0或者1都可以，但是考虑到除数不为0，应该去1
while (true) {
// 我觉得这里再加一句：其中一个数为1就直接返回1会更好
// 比如10，1就没必要一直减下去了，也算是剪枝
if (a == 1 || b == 1) return 1;
if (a > b) a -= b;
else if (b > a) b -= a;
else return a;
}
}
2. 辗转相除法
- 两数相等直接返回
- 否则，a、b的最大公约数等于 b 和 a%b 的最大公约数，重复这一过程直到两个数可以整除，返回a%b
或者其中一方为0(被整除了)，就返回另一方，考虑到1，所以一定是存在的
// 辗转相除法实现
int maxCommonDivisor(int a, int b) {
// 当其中一个为0，即被整除了
while (a*b) {
if (a > b) a %= b;
else if (b > a) b %= a;
// 其实也可以给上面加个=，处理a==b的情况
else return a;
}
// 返回不为0那个
return a > b ? a : b;
}