Tìm HCF/GCD (Ước chung lớn nhất) trong Python

HCF/GCD = số nguyên dương lớn nhất chia hết cả hai số. Ví dụ GCD(8,12)=4.

Thuật toán đơn giản

x = int(input("Nhập số thứ nhất: "))
y = int(input("Nhập số thứ hai: "))
if x > y:
    smaller = y
else:
    smaller = x
for i in range(1, smaller + 1):
    if (x % i == 0) and (y % i == 0):
        hcf = i
print("Ước chung lớn nhất của", x, "và", y, "là", hcf)

Tối ưu: Dùng thuật toán Euclid: math.gcd(a, b) (Python 3.5+) hoặc tự triển khai while b: a, b = b, a % b.