GCD & LCM

Thuật toán

GCD Sử dụng thuật toán của Euclid (khoảng 300 trước Công nguyên - một trong những thuật toán lâu đời nhất vẫn được sử dụng):

GCD(a, b):
  while b ≠ 0:
    a, b = b, a mod b
  return a

LCM có nguồn gốc từ GCD:

LCM(a, b) = |a × b| / GCD(a, b)

Đối với nhiều hơn hai số, hãy áp dụng theo cặp: GCD (a, b, c) = GCD (GCD (a, b), c).

Ví dụ