JavaScript 中用于计算 GCD 的欧几里得算法

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 8:12:17

在数学中，欧几里得算法是一种计算两个数的最大公约数 (GCD) 的方法，即两个数除以 1 而不留余数的最大数。

欧几里得算法基于这样的原理:如果将较大的数替换为其与较小的数之差，则两个数的最大公约数不会改变。

例如，21 是 252 和 105 的最大公约数(因为 252 = 21 × 12 和 105 = 21 × 5)，而同一个数字 21 也是 105 和 252 − 105 = 147 的最大公约数。

由于这种替换会减小两个数中较大的数，因此重复此过程会连续产生较小的数对，直到两个数相等。当发生这种情况时，它们就是原始两个数字的 GCD。

通过反转步骤，GCD 可以表示为两个原始数字乘以正整数或负整数之和，例如 21 = 5 × 105 + (−2) × 252。

我们需要编写一个 JavaScript 函数，该函数接受两个数字并使用欧几里得算法来计算它们的 GCD(最大公约数)

示例

以下是代码 −

const num1 = 252;
const num2 = 105;
const findGCD = (num1, num2) => {
   let a = Math.abs(num1);
   let b = Math.abs(num2);
   while (a && b && a !== b) {
      if(a > b){
         [a, b] = [a - b, b];
      }else{
         [a, b] = [a, b - a];
      };
   };
   return a || b;
};
console.log(findGCD(num1, num2));