Hướng dẫn tìm ước số chung trong Python chi tiết

Bài viết này sẽ hướng dẫn các bạn học sinh lớp 10 cách giải quyết bài toán tìm ước số chung lớn nhất (UCLN) của hai số nguyên trong Python. Chúng ta sẽ cùng nhau đi từ việc hiểu bản chất thuật toán toán học đến cách tự viết code xử lý lỗi, và cuối cùng là cách tận dụng sức mạnh của thư viện chuẩn Python để tối ưu hóa chương trình.

💡 Trả lời nhanh: Bài toán tìm ước số chung trong Python thường được giải quyết tối ưu bằng thuật toán chia liên tiếp Euclid (sử dụng vòng lặp while) hoặc sử dụng trực tiếp hàm math.gcd(a, b) có sẵn trong thư viện chuẩn để đảm bảo hiệu suất và độ chính xác cao nhất.

Đề bài 

Viết chương trình Python thực hiện các yêu cầu sau:

Input: Nhập vào từ bàn phím hai số nguyên a và b bất kỳ (bao gồm cả số âm và số 0).

Output: In ra màn hình một số nguyên dương là Ước số chung lớn nhất (UCLN) của a và b.

Ràng buộc: Mức độ trung cấp yêu cầu chương trình không bị lỗi (crash) khi người dùng nhập sai định dạng (ví dụ: nhập chữ cái, số thập phân). Phải bắt lỗi và yêu cầu nhập lại hoặc thông báo lỗi rõ ràng.

Phân tích bài toán ước số chung lớn nhất và nguyên lý Euclid

Bài toán tìm ước số chung trong Python yêu cầu chúng ta tìm ra một số nguyên dương lớn nhất có thể chia hết cho cả hai số đầu vào a và b. Để lập trình giải quyết vấn đề này, thay vì thử chia từng số từ 1 đến tập hợp số nhỏ hơn, các lập trình viên luôn ưu tiên sử dụng thuật toán Euclid vì tốc độ tính toán vượt trội của nó.

Về mặt dữ liệu, đầu vào là hai số nguyên. Tuy nhiên, trên thực tế, người dùng có thể nhập vào các giá trị không hợp lệ như chuỗi văn bản hoặc số thực. Vì chúng ta đang code ở mức độ trung cấp, việc sử dụng khối lệnh try...except để kiểm soát các ngoại lệ (exceptions) như ValueError là bắt buộc. Điều này giúp chương trình hoạt động bền bỉ hơn.

📌 Góc nhìn thực tế: Trong quá trình giảng dạy, thầy thấy rất nhiều bạn học sinh lớp 10 khi làm bài này thường quên mất việc xử lý số âm. Hệ quả là chương trình trả về UCLN là một số âm (sai định nghĩa toán học) hoặc rơi vào vòng lặp vô tận (infinite loop) khiến máy tính bị treo. Các em cần nhớ kỹ: UCLN luôn là số dương.

Giả định khi xử lý toán học

Để đảm bảo tính chặt chẽ, chúng ta thống nhất các nguyên tắc toán học sau cho bài toán này:

1. UCLN của hai số âm hoặc một âm một dương luôn là UCLN của giá trị tuyệt đối của chúng. Ví dụ: UCLN(-48, 18) = 6.

2. UCLN của một số a (khác 0) và số 0 luôn là chính giá trị tuyệt đối của a. Ví dụ: UCLN(5, 0) = 5.

3. Nếu cả hai số đều bằng 0, quy ước toán học không định nghĩa rõ ràng, nhưng trong lập trình Python, math.gcd(0, 0) trả về 0. Chúng ta sẽ tuân theo quy ước này của ngôn ngữ.

Chính vì những trường hợp biên (edge cases) phức tạp này, chúng ta sẽ đi qua 2 hướng tiếp cận bên dưới: một cách giúp các em rèn luyện tư duy logic thuật toán, và một cách giúp các em làm quen với phong cách code thực tế của kỹ sư phần mềm.

Cách 1: Tự code thuật toán Euclid tìm ước số chung bằng vòng lặp While 

Thuật toán Euclid tìm UCLN bằng cách lặp lại phép chia lấy dư a % b cho đến khi số dư b tiến về giá trị 0.

Ý tưởng thuật toán chia liên tiếp

Thay vì dùng vòng lặp for chạy ngược từ số nhỏ hơn về 1 (rất chậm nếu số lớn), thuật toán Euclid sử dụng tính chất: UCLN của hai số a và b cũng chính là UCLN của b và phần dư của phép chia a cho b. Chúng ta sẽ liên tục cập nhật giá trị của a thành b, và b thành phần dư, lặp đi lặp lại cho đến khi phần dư bằng 0. Lúc đó, giá trị của a (đã được lấy trị tuyệt đối) chính là kết quả cần tìm.

Các bước triển khai

1. Định nghĩa hàm solve(a, b).

2. Dùng hàm abs() để chuyển a và b thành số dương ngay từ đầu, tránh các rắc rối về dấu.

3. Tạo một vòng lặp while với điều kiện b khác 0 (while b != 0:).

4. Trong vòng lặp, tính số dư r = a % b.

5. Cập nhật a = b và b = r (Trong Python có thể viết gộp là a, b = b, a % b).

6. Khi vòng lặp kết thúc (tức là b = 0), trả về giá trị của a.

Minh họa tay thuật toán Euclid

Giả sử người dùng nhập a = 48, b = 18.

• Bước 1: Kiểm tra vòng lặp, b = 18 (khác 0) -> Chạy vòng lặp.

  Tính số dư: 48 % 18 = 12. Cập nhật: a mới = 18, b mới = 12.

• Bước 2: Kiểm tra vòng lặp, b = 12 (khác 0) -> Chạy vòng lặp.

  Tính số dư: 18 % 12 = 6. Cập nhật: a mới = 12, b mới = 6.

• Bước 3: Kiểm tra vòng lặp, b = 6 (khác 0) -> Chạy vòng lặp.

  Tính số dư: 12 % 6 = 0. Cập nhật: a mới = 6, b mới = 0.

• Bước 4: Kiểm tra vòng lặp, b = 0 -> Dừng vòng lặp. Trả về a = 6.

  Kết quả UCLN là 6. Hoàn toàn chính xác!

Đánh giá phương pháp

• Phù hợp người mới vì: Giúp các em học sinh hiểu sâu sắc về cách máy tính xử lý phép toán và làm quen với việc sử dụng vòng lặp while kết hợp với toán tử chia lấy dư %.

• Ưu điểm: Tự chủ được hoàn toàn logic, không phụ thuộc vào thư viện bên ngoài, dễ dàng tùy biến nếu bài toán có thêm các yêu cầu phụ.

• Nhược điểm: Cần phải cẩn thận khi code, nếu viết sai điều kiện cập nhật biến sẽ dễ dẫn đến việc chương trình chạy mãi không dừng.

• Độ phức tạp: O(log(min(a,b))) về thời gian / O(1) về bộ nhớ (rất tối ưu).

Cách 2: Dùng thư viện math.gcd tìm ước số chung lớn nhất cực nhanh 

Khác với Cách 1, cách này sử dụng hàm math.gcd() được tích hợp sẵn (built-in) trong thư viện chuẩn của Python, được viết bằng ngôn ngữ C nên có tốc độ thực thi không thể đánh bại.

Ý tưởng hàm built-in

Các kỹ sư phát triển ngôn ngữ Python đã lường trước việc lập trình viên sẽ rất thường xuyên phải tìm ước số chung. Do đó, họ đã viết sẵn thuật toán Euclid và đóng gói nó vào trong module math. Việc của chúng ta đơn giản là “nhập khẩu” (import) công cụ này ra và sử dụng, tiết kiệm được rất nhiều thời gian và công sức viết code.

Các bước thực hiện

1. Ở dòng đầu tiên của file code, viết lệnh import math.

2. Định nghĩa hàm solve_v2(a, b).

3. Bên trong hàm, chỉ cần dùng một câu lệnh duy nhất: return math.gcd(a, b).

4. Hàm này đã tự động xử lý lấy trị tuyệt đối cho số âm và xử lý trường hợp số 0 cực kỳ mượt mà.

Minh họa tay với hàm math

Giả sử gọi math.gcd(-48, 18):

• Python nhận đầu vào. Ngầm định chuyển đổi xử lý trị tuyệt đối.

• Python tự động chạy thuật toán tối ưu cấp thấp (bằng ngôn ngữ C) dưới nền.

• Trả về kết quả ngay lập tức: 6.

Khi nào nên dùng Cách 2?

Cách này là tiêu chuẩn trong môi trường thực tế. Khi các em tham gia các kỳ thi lập trình thi đấu (như HSG Tin học) ở phần thời gian ngặt nghèo, hoặc khi làm dự án thực tế sau này, hãy luôn ưu tiên dùng math.gcd(). Từ Python 3.9 trở đi, hàm math.gcd() cho phép tìm ước số chung lớn nhất của nhiều số cùng lúc, không chỉ giới hạn ở hai số.

Đánh giá thư viện chuẩn

• Ưu điểm: Code cực kỳ ngắn gọn (chỉ 1 dòng), dễ đọc, hoàn toàn miễn nhiễm với các lỗi sai logic thường gặp ở vòng lặp, xử lý các trường hợp biên (số âm, số 0) hoàn hảo 100%.

• Nhược điểm: Giấu đi bản chất thuật toán, nếu học sinh lạm dụng sẽ lười suy nghĩ về logic toán học đằng sau.

• Độ phức tạp: O(log(min(a,b))) về thời gian / O(1) về bộ nhớ. Tốc độ thực tế nhanh hơn Cách 1 do được tối ưu ở tầng C-API.

So sánh nhanh 2 cách 

Bảng này giúp bạn quyết định nên dùng cách nào mà không cần đọc lại toàn bài. Nhìn chung, kết quả tính toán của cả hai là giống hệt nhau.

Code Python ước số chung đầy đủ 

Cách 1 — Tự code thuật toán Euclid bằng vòng lặp While:

# Tên biến nhất quán với phần minh họa tay phía trên

def solve(a, b):
    """
    Hàm tìm Ước số chung lớn nhất (UCLN) của a và b bằng thuật toán Euclid.
    Nhận vào 2 số nguyên, trả về số nguyên dương là UCLN.
    """
    # Lấy giá trị tuyệt đối để đảm bảo UCLN luôn dương dù nhập số âm
    a = abs(a)
    b = abs(b)
    
    # Vòng lặp Euclid: lặp cho đến khi số dư b bằng 0
    while b != 0:
        a, b = b, a % b
        
    return a

# --- TEST NHANH (xóa hoặc comment lại trước khi nộp bài) ---
assert solve(48, 18) == 6
assert solve(-48, 18) == 6
assert solve(0, 5) == 5
assert solve(0, 0) == 0

# --- Nhập liệu với Try/Except (Mức độ Trung cấp) ---
if __name__ == "__main__":
    try:
        so_a = int(input("Nhập số nguyên a: "))
        so_b = int(input("Nhập số nguyên b: "))
        ucln = solve(so_a, so_b)
        print(f"Ước số chung lớn nhất của {so_a} và {so_b} là: {ucln}")
    except ValueError:
        print("Lỗi: Vui lòng chỉ nhập số nguyên hợp lệ (không nhập chữ cái hay số thực).")

# Đã kiểm tra: Python 3.12, 18-03-2026

Cách 2 — Sử dụng hàm math.gcd() có sẵn:

# Điểm khác với Cách 1: Phải import module math và code gọn hơn rất nhiều.

import math

def solve_v2(a, b):
    """Sử dụng hàm math.gcd tích hợp để tìm UCLN."""
    # Hàm gcd tự động xử lý số âm và trả về giá trị tuyệt đối dương
    return math.gcd(a, b)

# --- TEST NHANH ---
assert solve_v2(-48, 18) == 6

if __name__ == "__main__":
    try:
        so_a = int(input("Nhập số nguyên a: "))
        so_b = int(input("Nhập số nguyên b: "))
        print(f"UCLN tìm bằng math.gcd là: {solve_v2(so_a, so_b)}")
    except ValueError:
        print("Lỗi định dạng đầu vào. Vui lòng chạy lại và nhập số nguyên.")

Ví dụ chạy thử đầu vào và đầu ra 

Lỗi thường gặp khi viết hàm ước số chung trong Python 

Lỗi 1: Chương trình chạy mãi không dừng (Infinite Loop)

Hiện tượng: Sau khi nhập số liệu và nhấn Enter, con trỏ chuột nháy liên tục, chương trình không in ra kết quả cũng không kết thúc (treo máy). Output ra màn hình trống trơn thay vì in ra UCLN.

Nguyên nhân: Lỗi này xảy ra khi các em cố gắng tự code thuật toán tìm ước số chung nhưng sử dụng phép trừ liên tiếp (a = a - b) thay vì phép chia lấy dư (a % b). Nếu áp dụng thuật toán trừ mà không xử lý việc biến có thể trở thành số âm, điều kiện vòng lặp while a != b sẽ không bao giờ thỏa mãn, dẫn đến lặp vô tận. Hoặc do các em quên cập nhật giá trị của biến đếm trong vòng lặp.

Code sai:

# output sai là: Treo máy vĩnh viễn
def tim_ucln_loi(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = a - b  # Sai logic ở đây, b phải bằng b - a
    return a

Code đúng:

# output đúng là: 6 (sử dụng phép chia lấy dư an toàn hơn)
def tim_ucln_chuan(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

Lỗi 2: Trả về kết quả là số âm trái định nghĩa toán học

Hiện tượng: Output ra -6 thay vì 6 (với input là -48 và 18).

Nguyên nhân: Vì thuật toán chia lấy dư trong Python khi kết hợp với số âm sẽ bảo toàn dấu âm trong quá trình hoán đổi biến. Nếu các em không ép trị tuyệt đối (abs) cho hai biến ngay từ đầu bài, lúc kết thúc vòng lặp, giá trị của a có thể đang mang dấu âm. Mà theo quy ước toán học, ước số chung lớn nhất luôn phải là một số nguyên dương.

Code sai:

# output sai là: -6
def ucln_am(a, b):
    while b != 0:
        a, b = b, a % b
    return a # Quên lấy trị tuyệt đối

Code đúng:

# output đúng là: 6
def ucln_duong(a, b):
    a = abs(a)
    b = abs(b)
    while b != 0:
        a, b = b, a % b
    return a

Lỗi 3: Lỗi crash ValueError khi nhập dữ liệu từ bàn phím

Hiện tượng: Output ra một dòng chữ màu đỏ dài dằng dặc kết thúc bằng ValueError: invalid literal for int() with base 10.

Nguyên nhân: Vì hàm input() trong Python luôn trả về một chuỗi dạng văn bản (string). Khi chúng ta ép kiểu nó bằng int(), nếu người dùng cố tình nhập một chữ cái (ví dụ: ‘a’) hoặc một số thập phân (ví dụ: ‘3.14’), bộ chuyển đổi của Python sẽ không thể giải mã được và làm sập chương trình. Cần dùng try...except ValueError để chặn sự cố này.

Code sai:

# output sai là: Crash chương trình (ValueError)
a = int(input("Nhập a: "))
b = int(input("Nhập b: "))
print(math.gcd(a, b))

Code đúng:

# output đúng là: "Bạn phải nhập số nguyên!"
try:
    a = int(input("Nhập a: "))
    b = int(input("Nhập b: "))
    print(math.gcd(a, b))
except ValueError:
    print("Bạn phải nhập số nguyên!")

Lỗi 4: Truyền thẳng một danh sách (List) vào hàm math.gcd

Hiện tượng: Output ra lỗi TypeError: 'list' object cannot be interpreted as an integer.

Nguyên nhân: Vì hàm math.gcd() cốt lõi chỉ nhận vào các đối tượng có kiểu số nguyên rời rạc làm tham số. Khi các em muốn tìm ước chung của một mảng nhiều số và gõ math.gcd([12, 18, 24]), Python sẽ báo lỗi vì nó không hiểu danh sách này. Để xử lý với một list, các em cần phải giải nén (unpack) list đó bằng dấu sao * (áp dụng cho Python 3.9 trở lên) hoặc dùng hàm functools.reduce.

Code sai:

# output sai là: TypeError
import math
danh_sach = [12, 18, 24]
print(math.gcd(danh_sach))

Code đúng:

# output đúng là: 6
import math
danh_sach = [12, 18, 24]
print(math.gcd(*danh_sach)) # Dùng dấu * để giải nén mảng

Lỗi 5: Tính nhầm Bội chung nhỏ nhất (BCNN)

Hiện tượng: Output ra giá trị cực kỳ lớn, ví dụ input là 48 và 18 thì in ra 144 thay vì 6.

Nguyên nhân: Lỗi này xảy ra khi các bạn học sinh bị nhầm lẫn giữa định nghĩa ước số chung và bội chung nhỏ nhất. Cụ thể, các bạn áp dụng công thức BCNN = (a * b) / UCLN. Đây là một lỗi sai logic hoàn toàn do nhầm lẫn kiến thức toán học cơ sở chứ không phải lỗi cú pháp của ngôn ngữ lập trình Python.

Code sai:

# output sai là: 144
def nham_ucln_thanh_bcnn(a, b):
    import math
    return abs(a * b) // math.gcd(a, b) # Đây là công thức tìm BCNN

Code đúng:

# output đúng là: 6
def ucln_chuan_xac(a, b):
    import math
    return math.gcd(a, b)

Câu hỏi thường gặp 

Định nghĩa ước số chung lớn nhất trong Python là gì?

Ước số chung lớn nhất (UCLN) trong lập trình Python cũng tuân theo quy tắc toán học: là số nguyên dương lớn nhất có thể chia hết đồng thời cho cả hai (hoặc nhiều) số nguyên đầu vào. Trong Python, khái niệm này được biểu diễn chuẩn xác thông qua hàm math.gcd().

Thuật toán Euclid tìm ước số chung hoạt động như thế nào?

Thuật toán Euclid hoạt động dựa trên nguyên lý: phần dư của phép chia số lớn cho số bé vẫn chia hết cho chính ước số chung của chúng. Bằng cách lặp lại việc lấy phần dư của hai số cho đến khi một số tiến về 0, số còn lại sẽ thu nhỏ dần và chính xác là ước số chung cần tìm.

Làm thế nào để tìm ước số chung của 3 số trở lên bằng Python?

Từ phiên bản Python 3.9 trở đi, bạn có thể truyền thẳng nhiều tham số vào hàm có sẵn, ví dụ math.gcd(12, 18, 24) sẽ trả về 6. Nếu dùng phiên bản Python cũ hơn, bạn phải kết hợp module functools.reduce với hàm math.gcd để lặp qua từng cặp số trong mảng tuần tự.

Làm sao để áp dụng hàm math.gcd trong Python cho một danh sách (list) các số?

Nếu bạn có một mảng (list) chứa các số nguyên, ví dụ arr = [24, 36, 48], bạn không thể truyền thẳng biến arr vào hàm gcd. Bạn cần đặt dấu sao * trước tên biến: math.gcd(*arr) để hệ thống giải nén danh sách thành các số nguyên riêng biệt, giúp Python không bị báo lỗi TypeError.

Nên dùng vòng lặp While hay hàm math.gcd để tối ưu tốc độ tìm ước số chung?

Bạn luôn nên ưu tiên sử dụng math.gcd để tối ưu tốc độ tính toán. Hàm này được Python biên dịch ở tầng thấp bằng ngôn ngữ C nên có tốc độ thực thi nhanh hơn đáng kể so với việc chạy vòng lặp while trên tầng thông dịch bậc cao của Python, đặc biệt là khi xử lý các số có hàng ngàn chữ số.

Sự khác biệt giữa việc dùng thuật toán trừ liên tiếp và chia lấy dư (Euclid) là gì?

Cả hai cách đều là biến thể của Euclid, nhưng phép trừ liên tiếp (a = a - b) cực kỳ chậm và tốn bộ nhớ khi hai số có độ chênh lệch quá lớn (ví dụ tìm UCLN của 1 triệu và 2). Trong khi đó, phép chia lấy dư (a % b) rút ngắn toàn bộ số lần trừ đó chỉ bằng một nhịp tính toán duy nhất.

Tại sao code tìm ước số chung lớn nhất của tôi bị treo (infinite loop) khi chạy?

Code bị treo (lặp vô hạn) thường do bạn thiết lập điều kiện dừng vòng lặp while sai hoặc quên không cập nhật biến đếm bên trong vòng lặp. Cụ thể, nếu bạn dùng while b > 0: nhưng truyền vào số âm mà quên chưa dùng hàm abs(), điều kiện sẽ đánh giá sai và gây kẹt máy tính.

Kết luận

Qua bài học này, các bạn đã nắm vững cách tự xây dựng logic tìm ước số chung bằng vòng lặp while cũng như làm quen với sự ưu việt của thư viện chuẩn. Việc tự code tay (Cách 1) giúp bạn luyện tư duy cực tốt, nhưng trong thi đấu và làm việc thực tế, hãy luôn gọi math.gcd() (Cách 2) để đảm bảo code vừa nhanh vừa an toàn.

Nếu bạn đã giải được bài này bằng Cách 1, thử tự code lại bằng cách đệ quy (Recursion) không dùng gợi ý xem sao? Nếu ra kết quả khác hoặc có chỗ vướng khi làm bài tập, để lại câu hỏi ở phần bình luận để thầy hỗ trợ nhé!

Các khóa học liên quan: 

• Làm chủ Python trong 4 tuần

• Học python căn bản thông qua lập trình 1 game

• Python Excel cho người đi làm

• Học lập trình Python cho mọi lứa tuổi

• Thành thạo xử lý dữ liệu với Python

• Tập làm kĩ sư Amazon vận hành robot nông nghiệp với Python

Một số sản phẩm từ Python:

• Tool MMO: “Máy xay clip” chuẩn MMO cho TikTok, YouTube Shorts, Facebook Reels

Một số sách lập trình Python bạn hãy tham khảo

• Tiki: Python
• Shopee: Pyhon