Chương trình Python thuật toán Euclid cơ bản

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho hai số, cần tính GCD (ƯCLN) của hai số đó và hiển thị.

GCD là số lớn nhất chia hết cả hai. Euclid: chia liên tục đến khi dư = 0.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# Euclid cơ bản
def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

a = 11
b = 15
print("ƯCLN của", a, "&", b, "là =", gcd(a, b))

Kết quả

ƯCLN của 11 & 15 là = 1

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python thuật toán Euclid cơ bản.