最大公约数和最小公倍数：求解《1979. 找出数组的最大公约数》

什么是最大公约数，最小公倍数，如何求最大公约数和最小公倍数，求解《1979. 找出数组的最大公约数》

最大公约数（最大公因数）

• 能整除几个整数的最大数

最小公倍数

• 能**被整数*几个整数的最小**数
• 最小公倍数 = 公共质因数的乘积
• 最小公倍数 = 两数相乘 除以 最大公约数

求解最大公约数

辗转相除法（欧几里得法）

• 递归

  const gcd = (a, b) => b === 0 ? a : gcd(b, a % b)

• 迭代

  const gcd = (a, b) => {
  while (b) {
  const t = a
  a = b
  b = t % b
  } 
  return a
  }

更相减损法

• 递归

  const gcd = (a, b) => a === b ? a : a  > b ? gcd(a - b, b) : gcd(a, b - a)

• 迭代

  const gcd = (a, b) => {
  while (a !== b) a > b ? a -= b : b -= a 
  return a
  }

求解最小公倍数

const lcm = (a, b) => a * b / gcd(a, b)

例题

1979. 找出数组的最大公约数

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。 两个数的 最大公约数 是能够被两个数整除的最大正整数。

答案

求最大公约数的gcd函数可以用上面的方法来实现

var findGCD = function(nums) {
  const n = nums.length
  let min = 1001, max = 0
  for (let i = 0; i < n; i++) {
    if (min > nums[i]) min = nums[i]
    if (max < nums[i]) max = nums[i]
  }
  return gcd(min, max)
};
const gcd = (a, b) => {
  while (a !== b) a > b ? a -= b : b -= a
  return a
}