最大公約數英文詳解

一、什麼是最大公約數

最大公約數，英文為 Greatest Common Divisor（GCD），是指兩個或多個正整數公有的約數中最大的一個。

例如，12 和 18 的最大公約數是6。

在數學中，最大公約數的求解是非常常見的問題，因此有很多方法可以用來計算最大公約數。

二、求解最大公約數的方法

下面介紹幾種常見的計算最大公約數的方法。

1. 窮舉法

function gcd(a, b) {
  var min = Math.min(a, b);
  for (var i = min; i >= 1; i--) {
    if (a % i === 0 && b % i === 0) {
      return i;
    }
  }
}

console.log(gcd(12, 18)); // 輸出 6

窮舉法的思路是找出兩個數中的最小值，從這個最小值開始向下遍歷，找到第一個能夠同時整除 a 和 b 的數，即為最大公約數。

2. 利用歐幾里得演算法（輾轉相除法）

function gcd(a, b) {
  if (b === 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

console.log(gcd(12, 18)); // 輸出 6

歐幾里得演算法的思路是，用小的數去除大的數，然後用被除數除以餘數，直到餘數為0，此時被除數就是最大公約數。

3. 利用更相減損術

function gcd(a, b) {
  if (a === b) {
    return a;
  } else if (a > b) {
    return gcd(a - b, b);
  } else {
    return gcd(a, b - a);
  }
}

console.log(gcd(12, 18)); // 輸出 6

更相減損術的思路是，用大的數減去小的數，然後用得到的差和小的數繼續做差，直到兩個數相等，此時的值即為最大公約數。

三、最大公約數在演算法中的應用

最大公約數在演算法中有廣泛的應用，比如可以用最大公約數來求最小公倍數。在歐幾里得演算法中，可以優化求解多個數的最大公約數，而且最大公約數還可以用來判斷兩個數是否互質。

下面是一個使用歐幾里得演算法求解多個數的最大公約數的函數。

function gcd(nums) {
  var result = nums[0];
  for (var i = 1; i < nums.length; i++) {
    result = gcd2(result, nums[i]);
    if (result === 1) {
      return 1;
    }
  }
  return result;
}

function gcd2(a, b) {
  if (b === 0) {
    return a;
  } else {
    return gcd2(b, a % b);
  }
}

console.log(gcd([12, 18, 24])); // 輸出 6

四、總結

最大公約數在數學和演算法中都有著廣泛的應用。不同的求解方法有著各自的優缺點，可以根據具體的情況選擇不同的方法來計算最大公約數。