Thuật toán Euclid tính GCD (ƯCLN) trong JavaScript

Trong toán học, thuật toán Euclid là phương pháp tính ước chung lớn nhất (GCD) của hai số - số lớn nhất chia hết cả hai không dư.

Thuật toán Euclid dựa trên nguyên lý: GCD của hai số không thay đổi nếu số lớn hơn được thay bằng hiệu của nó với số nhỏ hơn. Ví dụ: 21 là GCD của 252 và 105 (252=21×12, 105=21×5), và 21 cũng là GCD của 105 và 252-105=147. Vì phép thay thế làm giảm số lớn hơn, lặp lại cho cặp số nhỏ dần cho đến khi hai số bằng nhau. Khi đó chúng là GCD của hai số gốc.

Đảo ngược các bước, GCD có thể biểu diễn thành tổng hai số gốc mỗi số nhân với số nguyên dương/âm, ví dụ: 21 = 5×105 + (-2)×252.

Chúng ta cần viết hàm nhận hai số và dùng thuật toán Euclid tính GCD của chúng.

Ví dụ

Code sau đây:

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));

Kết quả

Kết quả trên console:

21