Tìm GTĐB của hai số

Trong toán học, Số chia chung lớn nhất (GCD) là số nguyên lớn nhất có thể, chia cả hai số nguyên. Điều kiện là các số phải khác 0.

Chúng ta sẽ làm theo Thuật toán Euclide để tìm GCD của hai số.

Đầu vào và Đầu ra

Input:
Two numbers 51 and 34
Output:
The GCD is: 17

Thuật toán

findGCD(a, b)

Đầu vào: Hai số a và b.

Đầu ra: GCD của a và b.

Begin
   if a = 0 OR b = 0, then
      return 0
   if a = b, then
      return b
   if a > b, then
      return findGCD(a-b, b)
   else
      return findGCD(a, b-a)
End

Ví dụ

#include<iostream>
using namespace std;

int findGCD(int a, int b) {    //assume a is greater than b
   if(a == 0 || b == 0)
      return 0;    //as a and b are 0, the greatest divisior is also 0
   if(a==b)
      return b;    //when both numbers are same
   if(a>b)
      return findGCD(a-b, b);
   else
      return findGCD(a, b-a);
}

int main() {
   int a, b;
   cout << "Enter Two numbers to find GCD: "; cin >> a >> b;
   cout << "The GCD is: " << findGCD(a,b);
}

Đầu ra

Enter Two numbers to find GCD: 51 34
The GCD is: 17