Cho hai số nguyên a, b. Tìm ước chung lớn nhất (GCD) bằng thuật toán Euclid đệ quy.
Ví dụ: a = 25, b = 45 → 5.
Thuật toán Euclid (phiên bản trừ)
- Nếu
a == b→ trả vềa. - Nếu
a < b→ hoán đổi:gcd(b, a). - Ngược lại:
gcd(b, a - b).
Lưu ý: Phiên bản lấy modulo (gcd(b, a % b)) nhanh hơn.
Ví dụ mã nguồn
def gcd(a, b):
if a == b:
return a
elif a < b:
return gcd(b, a)
else:
return gcd(b, a - b)
a = 25
b = 45
print(gcd(a, b)) # 5
Đầu vào / Đầu ra
Input: 25, 45
Output: 5