最大公约数和最小公倍数问题


最大公约数的计算,用到辗转相除法

例如:求 gcd(24, 10) ,可以转换为 gcd(10,4), 然后是 gcd(4,2) ,然后是(2,0),最好得出结果是2

方法1:

function gcd(a, b) {
  var temp 
  if (a < b) temp = b, b = a, a = temp
  while (b != 0) {
    temp = b
    b = a % b
    a = temp
  } 
  return a
}

方法2:

function gcd2(a,b) {
  var temp 
  if (a < b) temp = b, b = a, a = temp
  if (a == b || b == 0) return a
  return gcd2(b, a % b)
}

多个数求公约数:

function gcd_multiple(...args) {
  while (args.length > 1) {
    args.splice(0,2,gcd2(args[0],args[1]))
  }
  return args[0]
}

最小公倍数的计算,两数的乘积/最大公约数

function lcm(a, b) {
  return a * b / gcd2(a,b)
}
function lcm_multiple(...args) {
  while (args.length > 1) {
    args.splice(0,2,lcm(args[0],args[1]))
  }
  return args[0]
}