CodeUtility
Lập trình thông minh, làm việc hiệu quả!
Thuật toán Python

Thuật toán Euclid tìm ƯCLN trong Python

Tìm ước chung lớn nhất chỉ trong vài bước bằng mẹo chia lấy dư của Euclid, rồi so sánh với math.gcd.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Ước chung lớn nhất là gì
  • Thuật toán Euclid
  • math.gcd trong thư viện chuẩn
Chạy trong trình biên dịch Python →
gcd(48, 18)
  1. 48 % 18 = 12→ (18, 12)
  2. 18 % 12 = 6→ (12, 6)
  3. 12 % 6 = 0→ gcd = 6

Thay cặp số bằng (b, a % b)

Ước chung lớn nhất (UCLN) của hai số nguyên là số nguyên dương lớn nhất mà cả hai số đều chia hết. Thuật toán Euclid tìm UCLN rất nhanh dựa trên một tính chất đơn giản, UCLN của a và b cũng bằng UCLN của b và phần dư khi chia a cho b.

Những điểm quan trọng

  1. gcd(a, b) bằng gcd(b, a % b).
  2. Lặp lại cho đến khi số dư bằng 0; số còn lại là đáp án.
  3. math.gcd(48, 18) cho cùng kết quả.

Khi nào nên sử dụng?

  • Rèn luyện tư duy giải quyết vấn đề và hiểu cách thuật toán hoạt động qua từng bước.
  • Chọn được cách giải phù hợp khi cần xử lý nhiều dữ liệu hoặc cần chương trình chạy nhanh hơn.
  • Chuẩn bị cho các kỳ thi, bài tập và phỏng vấn lập trình.

Code ví dụ

Chạy code →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

6

Giải thích code

Ở mỗi bước, cặp số (first, second) được thay bằng (second, first % second). Khi phần dư bằng 0, giá trị còn lại trong first chính là UCLN, nên UCLN của 48 và 18 là 6. Hàm abs() đảm bảo kết quả luôn dương. Số bước cần thực hiện tăng rất chậm theo độ lớn của số, khoảng O(log n).

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

  1. Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Chạy trong trình biên dịch Python →

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách