题解 | #最大公约数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求出a、b的最大公约数。
 * @param a int
 * @param b int
 * @return int
 */
function gcd(a, b) {
    // write code here
    // 暴力解法：用c来记录能被这两个数整除的数字，
    // 从1开始，先找出两个中最小的那个，当作循环的限制条件
    // 只要满足a%i===0&&b%i===0，就将i的值赋给c,最后返回c（最后返回的一定是最大的那个）
    let c = 1;
    const mi = Math.min(a, b);
    if (a % b === 0) return b;
    if (b % a === 0) return a;
    for (let i = 0; i < mi; i++) {
        if (a % i === 0 && b % i === 0) {
            c = i;
        }
    }
    return c;

    // 辗转相除法（符合题目中要求的时间空间复杂度）
    // 例子：假如需要求 434 和 652 的最大公约数,用欧几里得算法，是这样进行的： 434 / 652 = 0 (余 434) 652 / 434 = 1(余218) 434 / 218 = 1(余216) 218 / 216 = 1 (余2) 216 / 2 = 108(余0) 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 434 和 652 的最大公约数 2
    // 核心算法：gcd(a,b)=gcd(b,amodb)
    // if (a % b === 0) {
    //     return b;
    // } else {
    //     return gcd(b, a % b);
    // }
}