CTDL và giải thuật - Tìm ước chung lớn nhất của 2 số

Nhập vào hai số nguyên a và b. Hãy tìm ước chung lớn nhất của chúng.

(Ước chung lớn nhất của hai số nguyên là một số lớn nhất mà cả hai số đó đều chia hết).

Ví dụ:

  • Test mẫu 1:
     
    Input Output
    10 15 5

    Với a = 10, b = 15 thì kết quả mong muốn là 5.
     
  • Test mẫu 2:
     
    Input Output
    3 7 1

    Với a = 3, b = 7 thì kết quả mong muốn là 1.

Hướng dẫn bài tập.

Gợi ý: Ucln(a, b) = Ucln(b, a%b).

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

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

int main(){
    int a, b;
    cin >> a >> b;
    cout << ucln(a, b);
}