定义

能够整除多个整数的最大正整数。而多个整数不能都为零。

求两个整数最大公约数主要的方法:

• 穷举法 (opens new window): 分别列出两整数的所有约数, 并找出最大的公约数。

• 素因数分解 (opens new window): 分别列出两数的素因数分解式, 并计算共同项的乘积。

• 短除法 (opens new window): 两数除以其共同素因数, 直到两数互素时, 所有除数的乘积即为最大公约数。

• 辗转相除法 (opens new window): 又称欧几里得算法 (Euclidean Algorithm), 两数相除, 取余数重复进行相除, 直到余数为 0 时, 前一个除数即为最大公约数。

Note

$gcm(a, b) \times lcm(a, b) = |ab|$

实现代码

/*
 * @Author: Rainy
 * @Date: 2020-01-30 11:42:57
 * @LastEditors  : Rainy
 * @LastEditTime : 2020-01-31 13:28:43
 */

// the greatest common divisor
export function gcd_enumeration(a: number, b: number): number {
  let gcd = 1;

  let smaller = Math.min(a, b);

  for (let i = 2; i <= smaller; i++) {
    if ((a % i === 0) && (b % i === 0)) {
      gcd = i;
    }
  }

  return gcd;
}

export function gcd_division_recursive(a: number, b: number): number {
  if (b === 0) {
    return a;
  }

  return gcd_division_recursive(b , a % b);
}

export function gcd_sub_recursive(a: number, b: number): number {
  if (a === b) {
    return a;
  }

  return a > b ? gcd_sub_recursive(a - b, b) : gcd_sub_recursive(a, b - a);
}

export function gcd_optimal(a: number, b: number): number {
  if (a === b) {
    return a;
  }

  if ((a & 1) === 0 && (b & 1) === 0) {
    return gcd_optimal(a >> 1, b >> 1);
  } else if ((a & 1) === 0 && (b & 1) !== 0) {
    return gcd_optimal(a >> 1, b);
  } else if ((a & 1) !== 0 && (b & 1) === 0) {
    return gcd_optimal(a, b >> 1);
  } else {
    const max = Math.max(a, b);
    const min = Math.min(a, b);
    return gcd_optimal(max - min, min);
  }
}

参考资料

最大公约数 - wiki (opens new window)