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ớia = 10, b = 15
thì kết quả mong muốn là5
.
- Test mẫu 2:
Input Output 3 7 1
Vớia = 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);
}