Chương trình C cho thuật toán Euclid cơ bản

Ở đây chúng ta sẽ thấy thuật toán Euclid để tìm GCD của hai số. GCD (Ước chung lớn nhất) có thể dễ dàng tìm được bằng thuật toán Euclid. Có hai cách tiếp cận khác nhau. Một là lặp, một là đệ quy. Ở đây chúng ta sẽ dùng thuật toán Euclid đệ quy.

Thuật toán

EuclideanAlgorithm(a, b)

begin
  if a is 0, then
    return b
  end if
  return gcd(b mod a, a)
end

Ví dụ

#include<iostream>
using namespace std;

int euclideanAlgorithm(int a, int b) {
  if (a == 0)
    return b;
  return euclideanAlgorithm(b%a, a);
}

main() {
  int a, b;
  cout << "Enter two numbers: ";
  cin >> a >> b;
  cout << "GCD " << euclideanAlgorithm(a, b);
}

Kết quả

Enter two numbers: 12 16
GCD 4