Tìm Ước Chung Lớn Nhất Python: 10 Cách Viết Code Đơn Giản & Hiệu Quả Nhất

Trong lập trình, việc xử lý các bài toán số học như tìm ước chung lớn nhất (UCLN) là nền tảng quan trọng, xuất hiện trong nhiều tình huống như rút gọn phân số, tối ưu thuật toán hay giải quyết các bài toán chia đều. Với ngôn ngữ Python, bạn có thể triển khai bài toán này theo nhiều cách khác nhau, phù hợp với từng mục đích sử dụng. Bài viết dưới đây của APTECH SAIGON sẽ hướng dẫn chi tiết cách tìm ước chung lớn nhất Python thông qua nhiều phương pháp dễ hiểu và hiệu quả.

Ước chung lớn nhất (UCLN) là gì?

Ước chung lớn nhất (UCLN) của hai hay nhiều số nguyên là số lớn nhất có thể chia hết cho tất cả các số đó. Nói cách khác, UCLN là ước chung có giá trị lớn nhất trong tập hợp các ước chung của các số đang xét. Đây là một khái niệm rất quan trọng trong toán học và được ứng dụng rộng rãi trong lập trình, đặc biệt khi xử lý các bài toán liên quan đến phân số, chia đều hoặc tối ưu thuật toán.

Ví dụ: UCLN của 12 và 18 là 6 vì:

• • Các ước của 12: 1, 2, 3, 4, 6, 12
  • Các ước của 18: 1, 2, 3, 6, 9, 18
  • Ước chung: 1, 2, 3, 6 → lớn nhất là 6

! Một số trường hợp đặc biệt cần lưu ý:

• • UCLN(a, 0) = |a| (với a ≠ 0)
  • UCLN(0, 0) không xác định
  • Với số âm, ta thường lấy giá trị tuyệt đối trước khi tính UCLN.

Tư duy tìm ước chung lớn nhất trong Python

Để giải quyết hiệu quả bài toán tìm ước chung lớn nhất Python, bạn cần hiểu rõ cách tiếp cận và lựa chọn thuật toán phù hợp thay vì chỉ áp dụng máy móc. Dưới đây là những tư duy quan trọng giúp bạn xây dựng cách giải nhanh chóng và tối ưu hơn:

Nguyên lý cơ bản

Nguyên lý cơ bản để tìm ước chung lớn nhất (UCLN) của hai số là dựa trên việc xác định các ước chung của chúng, sau đó chọn ra giá trị lớn nhất trong số các ước đó. Đây là cách tiếp cận trực quan và dễ hiểu nhất, đặc biệt phù hợp với người mới bắt đầu học lập trình.

Cách thực hiện:

• • Xác định tất cả các ước của số thứ nhất
  • Xác định tất cả các ước của số thứ hai
  • Tìm các ước chung giữa hai tập hợp trên
  • Chọn giá trị lớn nhất trong các ước chung đó → chính là UCLN

Ví dụ với hai số 12 và 18:

• • Ước của 12: 1, 2, 3, 4, 6, 12
  • Ước của 18: 1, 2, 3, 6, 9, 18
  • Ước chung: 1, 2, 3, 6 → UCLN là 6

Tuy phương pháp này dễ hiểu, nhưng khi làm việc với các số lớn, việc liệt kê tất cả các ước sẽ tốn nhiều thời gian và không hiệu quả. Vì vậy, trong thực tế lập trình, người ta thường sử dụng các thuật toán tối ưu hơn để tìm UCLN nhanh chóng.

Tối ưu thuật toán

Để tìm ước chung lớn nhất một cách hiệu quả hơn, chúng ta cần tối ưu thuật toán thay vì liệt kê toàn bộ các ước. Phương pháp phổ biến và mạnh mẽ nhất là thuật toán Euclid, dựa trên một tính chất quan trọng: UCLN của hai số không thay đổi nếu ta thay số lớn hơn bằng phần dư của phép chia giữa hai số đó.

Cách thực hiện:

• • Nếu b = 0 → UCLN(a, b) = a
  • Nếu b ≠ 0 → thay (a, b) bằng (b, a % b)
  • Lặp lại quá trình cho đến khi b = 0

Ví dụ với a = 48, b = 18:

• • 48 % 18 = 12 → chuyển thành (18, 12)
  • 18 % 12 = 6 → chuyển thành (12, 6)
  • 12 % 6 = 0 → dừng lại → UCLN là 6

Phương pháp này có nhiều ưu điểm nổi bật như không cần liệt kê toàn bộ các ước của số, giúp giảm đáng kể số bước tính toán, đồng thời có độ phức tạp thấp (khoảng O(log n)) nên hoạt động rất hiệu quả ngay cả với các số lớn. Chính vì vậy, thuật toán Euclid trở thành phương pháp tiêu chuẩn khi tìm ước chung lớn nhất trong Python cũng như trong nhiều ngôn ngữ lập trình khác.

￭ Xem Thêm: Kiểm Tra Số Nguyên Tố Python: 5 Cách Viết Code Đơn Giản & Tối Ưu Nhất

Tổng hợp 10 phương pháp tìm ước chung lớn nhất Python hiệu quả nhất

Trên thực tế, có nhiều cách khác nhau để tìm ước chung lớn nhất Python. Mỗi phương pháp sẽ có ưu điểm riêng tùy vào mục đích sử dụng và mức độ tối ưu mong muốn. Trong phần này, APTECH SAIGON sẽ hướng dẫn 10 phương pháp phổ biến và hiệu quả nhất, giúp bạn áp dụng linh hoạt trong từng bài toán cụ thể:

Cách 1: Duyệt ước chung (brute force)

Phương pháp duyệt ước chung (brute force) là cách đơn giản và trực quan nhất để tìm ước chung lớn nhất của hai số. Ý tưởng chính là liệt kê tất cả các ước chung của hai số, sau đó chọn ra giá trị lớn nhất trong số đó.

Cách thực hiện:

• • Duyệt các số từ 1 đến min(a, b)
  • Với mỗi số i, kiểm tra nếu i chia hết cho cả a và b
  • Nếu thỏa điều kiện, cập nhật giá trị UCLN
  • Sau khi duyệt xong, giá trị lớn nhất tìm được chính là UCLN

Dưới đây là ví dụ minh họa:

a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) gcd = 1 for i in range(1, min(a, b) + 1):    if a % i == 0 and b % i == 0:        gcd = i print(“UCLN là:”, gcd)

Giải thích:

• • Sử dụng vòng lặp for để duyệt các giá trị có thể là ước chung
  • Kiểm tra điều kiện chia hết cho cả hai số
  • Luôn cập nhật giá trị lớn nhất tìm được

Ví dụ:

• • a = 12, b = 18 → UCLN là 6
  • a = 8, b = 20 → UCLN là 4

Ưu điểm của phương pháp này là dễ hiểu và phù hợp với người mới học. Tuy nhiên, nhược điểm là phải duyệt nhiều lần lặp nên sẽ kém hiệu quả khi làm việc với các số lớn.

Cách 2: Thuật toán trừ liên tiếp (Euclid cổ điển)

Thuật toán trừ liên tiếp là phiên bản cổ điển của thuật toán Euclid, trong đó ta không sử dụng phép chia dư mà thay vào đó liên tục trừ số nhỏ hơn khỏi số lớn hơn cho đến khi hai số bằng nhau. Khi hai số trở nên bằng nhau, giá trị đó chính là ước chung lớn nhất.

Cách thực hiện:

• • Nếu a = b → UCLN là a (hoặc b)
  • Nếu a > b → thay a = a – b
  • Nếu b > a → thay b = b – a
  • Lặp lại cho đến khi a = b

Dưới đây là ví dụ minh họa:

a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) while a != b:    if a > b:        a -= b    else:        b -= a print(“UCLN là:”, a)

Giải thích:

• • Mỗi bước sẽ làm giảm giá trị của một trong hai số
  • Quá trình lặp lại cho đến khi hai số bằng nhau
  • Khi đó, giá trị chung chính là UCLN

Ví dụ: a = 48, b = 18

• • 48 – 18 = 30 → (30, 18)
  • 30 – 18 = 12 → (12, 18)
  • 18 – 12 = 6 → (12, 6)
  • 12 – 6 = 6 → (6, 6) → UCLN = 6

Ưu điểm của phương pháp này là dễ hiểu và giúp bạn hình dung rõ cách hoạt động của thuật toán Euclid. Tuy nhiên, nhược điểm là số lần lặp nhiều hơn so với phương pháp chia dư, nên kém hiệu quả khi xử lý các số lớn.

Cách 3: Thuật toán Euclid (chia dư)

Thuật toán Euclid là phương pháp phổ biến và hiệu quả nhất để tìm ước chung lớn nhất của hai số. Ý tưởng cốt lõi của thuật toán này là: UCLN của hai số không thay đổi nếu ta thay số lớn hơn bằng phần dư của phép chia giữa hai số đó, và lặp lại quá trình cho đến khi phần dư bằng 0.

Cách thực hiện:

• • Nếu b = 0 → UCLN(a, b) = a
  • Nếu b ≠ 0 → thay (a, b) bằng (b, a % b)
  • Lặp lại cho đến khi b = 0

Dưới đây là ví dụ minh họa:

a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) while b != 0:    a, b = b, a % b print(“UCLN là:”, a)

Giải thích:

• • Sử dụng vòng lặp while để liên tục cập nhật giá trị
  • Mỗi bước, a sẽ nhận giá trị của b và b nhận phần dư của phép chia
  • Khi b = 0, giá trị của a chính là UCLN

Ví dụ: a = 48, b = 18

• • 48 % 18 = 12 → (18, 12)
  • 18 % 12 = 6 → (12, 6)
  • 12 % 6 = 0 → dừng → UCLN = 6

Ưu điểm của thuật toán này là rất nhanh, không cần liệt kê ước và có độ phức tạp thấp, nên được sử dụng rộng rãi trong thực tế cũng như trong các bài toán lập trình.

￭ Xem Thêm: Dấu // Trong Python Là Gì? Tổng Hợp Các Toán Tử Trong Lập Trình Python

Cách 4: Dùng đệ quy (recursion)

Phương pháp đệ quy là một cách triển khai khác của thuật toán Euclid, giúp code trở nên ngắn gọn và dễ hiểu hơn khi bạn đã quen với tư duy hàm gọi lại chính nó. Thay vì sử dụng vòng lặp, ta xây dựng một hàm gọi lại chính nó cho đến khi đạt điều kiện dừng.

Cách thực hiện:

• • Nếu b = 0 → trả về a (điều kiện dừng)
  • Nếu b ≠ 0 → gọi lại hàm với tham số (b, a % b)
  • Lặp lại cho đến khi b = 0

Dưới đây là ví dụ minh họa:

def gcd(a, b):    if b == 0:        return a    return gcd(b, a % b) a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) print(“UCLN là:”, gcd(a, b))

Giải thích:

• • Hàm gcd(a, b) sẽ liên tục gọi lại chính nó với bộ tham số mới
  • Mỗi lần gọi sẽ giảm dần giá trị của b
  • Khi b = 0, hàm trả về a và kết thúc toàn bộ quá trình

Ví dụ:

• • gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → kết quả là 6

Cách 5: Sử dụng thư viện math.gcd

Sử dụng thư viện có sẵn là cách nhanh nhất và tiện lợi nhất để tìm ước chung lớn nhất trong Python. Thư viện math đã cung cấp sẵn hàm gcd(), giúp bạn tính UCLN chỉ với một dòng code mà không cần tự triển khai thuật toán.

Cách thực hiện:

• • Import thư viện math
  • Sử dụng hàm math.gcd(a, b) để tính UCLN

Dưới đây là ví dụ minh họa:

import math a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) print(“UCLN là:”, math.gcd(a, b))

Giải thích:

• • Hàm math.gcd(a, b) sẽ tự động áp dụng thuật toán tối ưu bên trong (thường là Euclid)
  • Trả về kết quả UCLN của hai số a và b

Ví dụ:

• • a = 12, b = 18 → Kết quả: 6
  • a = 20, b = 30 → Kết quả: 10

Ưu điểm của phương pháp này là đơn giản, dễ sử dụng, chạy nhanh và hạn chế lỗi trong quá trình cài đặt. Đây là lựa chọn phù hợp khi bạn cần viết code gọn gàng hoặc áp dụng trong các dự án thực tế.

Cách 6: Tìm ước chung lớn nhất của nhiều số

Trong thực tế, bạn không chỉ cần tìm ước chung lớn nhất của hai số mà còn có thể phải xử lý nhiều số cùng lúc. Khi đó, ta có thể mở rộng thuật toán bằng cách áp dụng UCLN lần lượt cho từng cặp số, cho đến khi thu được kết quả cuối cùng.

Cách thực hiện:

• • Tính UCLN của hai số đầu tiên
  • Dùng kết quả đó để tiếp tục tính với số tiếp theo
  • Lặp lại cho đến hết danh sách

Dưới đây là ví dụ minh họa:

from math import gcd from functools import reduce numbers = list(map(int, input(“Nhập các số: “).split())) result = reduce(gcd, numbers) print(“UCLN là:”, result)

Giải thích:

• • Hàm reduce() giúp áp dụng hàm gcd lên toàn bộ danh sách
  • Ban đầu tính gcd của 2 phần tử đầu, sau đó tiếp tục với phần tử tiếp theo
  • Quá trình lặp lại cho đến khi hết danh sách

Ví dụ:

• • Nhập: 12 18 24 → Kết quả: 6
  • Nhập: 8 16 32 → Kết quả: 8

Ưu điểm của phương pháp này là linh hoạt, dễ mở rộng và phù hợp khi làm việc với dữ liệu dạng danh sách. Đây là cách tiếp cận rất hữu ích trong các bài toán thực tế liên quan đến nhiều giá trị.

Cách 7: Phân tích thừa số nguyên tố

Phương pháp phân tích thừa số nguyên tố dựa trên việc biểu diễn mỗi số thành tích các số nguyên tố, sau đó tìm các thừa số chung với số mũ nhỏ nhất để xác định ước chung lớn nhất. Đây là cách tiếp cận mang tính toán học rõ ràng, giúp bạn hiểu sâu hơn về bản chất của UCLN.

Cách thực hiện:

• • Phân tích từng số thành tích các thừa số nguyên tố
  • Xác định các thừa số nguyên tố chung giữa các số
  • Lấy số mũ nhỏ nhất của mỗi thừa số chung
  • Nhân lại các thừa số đó để thu được UCLN

Dưới đây là ví dụ minh họa:

def prime_factors(n):    factors = {}    i = 2    while i * i <= n:        while n % i == 0:            factors[i] = factors.get(i, 0) + 1            n //= i        i += 1    if n > 1:        factors[n] = 1    return factors def gcd_from_factors(a, b):    fa = prime_factors(a)    fb = prime_factors(b)       gcd = 1    for key in fa:        if key in fb:            gcd *= key ** min(fa[key], fb[key])    return gcd a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) print(“UCLN là:”, gcd_from_factors(a, b))

Giải thích:

• • Hàm prime_factors() dùng để phân tích một số thành các thừa số nguyên tố
  • So sánh hai kết quả để tìm các thừa số chung
  • Lấy số mũ nhỏ nhất và nhân lại để ra UCLN

Ví dụ:

• • a = 12 = 2² × 3
  • b = 18 = 2 × 3²
    → UCLN = 2¹ × 3¹ = 6

Ưu điểm của phương pháp này là dễ hiểu về mặt lý thuyết và giúp củng cố kiến thức toán học. Tuy nhiên, nhược điểm là chậm hơn so với thuật toán Euclid, đặc biệt khi làm việc với các số lớn.

￭ Xem Thêm: Học Python Để Làm Gì? Cơ Hội Việc Làm & Mức Lương Python Developer [2026]

Cách 8: Thuật toán Binary GCD (Stein)

Thuật toán Binary GCD (hay còn gọi là thuật toán Stein) là một phương pháp tìm ước chung lớn nhất dựa trên các phép toán nhị phân, thay vì sử dụng phép chia như thuật toán Euclid. Ý tưởng chính là tận dụng các phép chia cho 2 (dịch bit) để giảm số bước tính toán, từ đó cải thiện hiệu suất trong một số trường hợp.

Cách thực hiện:

• • Nếu một trong hai số bằng 0 → UCLN là số còn lại
  • Nếu cả hai số đều chẵn → UCLN = 2 × gcd(a/2, b/2)
  • Nếu một số chẵn, một số lẻ → chia số chẵn cho 2
  • Nếu cả hai đều lẻ → lấy hiệu hai số rồi chia cho 2
  • Lặp lại cho đến khi hai số bằng nhau

Dưới đây là ví dụ minh họa:

def binary_gcd(a, b):    if a == 0:        return b    if b == 0:        return a    if a % 2 == 0 and b % 2 == 0:        return 2 * binary_gcd(a // 2, b // 2)    elif a % 2 == 0:        return binary_gcd(a // 2, b)    elif b % 2 == 0:        return binary_gcd(a, b // 2)    elif a >= b:        return binary_gcd((a – b) // 2, b)    else:        return binary_gcd(a, (b – a) // 2) a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) print(“UCLN là:”, binary_gcd(a, b))

Giải thích:

• • Thuật toán sử dụng các phép chia cho 2 thay vì phép chia dư
  • Dựa vào tính chẵn/lẻ để xử lý các trường hợp khác nhau
  • Giảm dần giá trị của a và b cho đến khi tìm được UCLN

Ví dụ:

• • a = 48, b = 18 → UCLN = 6

Ưu điểm của phương pháp này là không cần sử dụng phép chia dư, phù hợp với hệ thống xử lý nhị phân và có thể nhanh hơn trong một số trường hợp. Tuy nhiên, thuật toán này phức tạp hơn về mặt cài đặt so với Euclid nên ít được sử dụng trong các bài toán cơ bản.

Cách 9: Thuật toán Euclid mở rộng

Thuật toán Euclid mở rộng là phiên bản nâng cao của thuật toán Euclid, không chỉ giúp tìm ước chung lớn nhất mà còn xác định được hai số nguyên x và y sao cho: ax + by = gcd(a, b). Phương pháp này thường được sử dụng trong các bài toán nâng cao như giải phương trình Diophantine hoặc các thuật toán mật mã.

Cách thực hiện:

• • Nếu b = 0 → trả về (a, 1, 0)
  • Nếu b ≠ 0 → gọi đệ quy với (b, a % b)
  • Từ kết quả trả về, tính lại hệ số x và y

Dưới đây là ví dụ minh họa:

def extended_gcd(a, b):    if b == 0:        return a, 1, 0    gcd, x1, y1 = extended_gcd(b, a % b)    x = y1    y = x1 – (a // b) * y1    return gcd, x, y a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) gcd, x, y = extended_gcd(a, b) print(“UCLN là:”, gcd) print(“Hệ số x, y:”, x, y)

Giải thích:

• • Hàm extended_gcd() trả về ba giá trị: UCLN và hai hệ số x, y
  • Thuật toán hoạt động tương tự Euclid nhưng bổ sung bước tính toán hệ số
  • Các hệ số này giúp biểu diễn UCLN dưới dạng tổ hợp tuyến tính

Ví dụ:

• • a = 30, b = 20 → UCLN = 10
  • Có thể tìm được x, y sao cho: 30x + 20y = 10

Ưu điểm của phương pháp này là mạnh mẽ và có nhiều ứng dụng trong các bài toán nâng cao. Tuy nhiên, với nhu cầu chỉ tìm UCLN thông thường, bạn không nhất thiết phải sử dụng đến thuật toán này.

Cách 10: Sử dụng NumPy để tính UCLN mảng lớn

Khi làm việc với dữ liệu lớn hoặc các bài toán xử lý mảng trong Python, bạn có thể sử dụng thư viện NumPy để tính ước chung lớn nhất một cách nhanh chóng và hiệu quả. NumPy cung cấp hàm gcd có thể áp dụng trực tiếp trên mảng, giúp bạn xử lý nhiều giá trị cùng lúc mà không cần viết vòng lặp thủ công.

Cách thực hiện:

• • Cài đặt và import thư viện NumPy
  • Sử dụng hàm np.gcd.reduce() để tính UCLN của toàn bộ mảng

Dưới đây là ví dụ minh họa:

import numpy as np arr = list(map(int, input(“Nhập các số: “).split())) arr_np = np.array(arr) result = np.gcd.reduce(arr_np) print(“UCLN là:”, result)

Giải thích:

• • Chuyển danh sách sang mảng NumPy để xử lý
  • Hàm np.gcd.reduce() sẽ lần lượt tính UCLN giữa các phần tử trong mảng
  • Kết quả cuối cùng là UCLN của toàn bộ dãy số

Ví dụ:

• • Nhập: 12 18 24 → Kết quả: 6
  • Nhập: 20 40 60 → Kết quả: 20

Ưu điểm của phương pháp này là rất nhanh khi xử lý dữ liệu lớn và phù hợp với các bài toán liên quan đến khoa học dữ liệu hoặc xử lý số lượng phần tử lớn. Tuy nhiên, bạn cần cài đặt thêm thư viện NumPy và phương pháp này có thể không cần thiết đối với các bài toán nhỏ.

￭ Xem Thêm: 20+ Ứng Dụng Của Python Trong Các Lĩnh Vực Thực Tế [Cập Nhật 2026]

Bài tập tìm ước chung lớn nhất Python kèm code mẫu chi tiết

Sau khi đã nắm vững các phương pháp tìm ước chung lớn nhất Python, việc luyện tập với các bài toán cụ thể sẽ giúp bạn hiểu sâu hơn và áp dụng linh hoạt trong thực tế. Dưới đây là một số bài tập kèm code mẫu chi tiết để bạn củng cố kiến thức và nâng cao kỹ năng lập trình:

Bài 1: Tìm ước chung lớn nhất của 2 số bằng Python

Yêu cầu: Nhập hai số nguyên a và b, tính và in ra ước chung lớn nhất của chúng.

Cách làm:

• Sử dụng thuật toán Euclid (chia dư) để tối ưu hiệu suất
• Lặp lại quá trình cho đến khi một trong hai số bằng 0

Dưới đây là ví dụ minh họa:

a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) while b != 0:    a, b = b, a % b print(“UCLN là:”, a)

Giải thích:

• • Mỗi bước, giá trị của a và b được cập nhật theo nguyên tắc Euclid
  • Khi b = 0, giá trị của a chính là UCLN

Ví dụ:

• • Nhập a = 12, b = 18 → Kết quả: 6
  • Nhập a = 20, b = 30 → Kết quả: 10

Bài 2: Tìm ước chung lớn nhất của 3 số Python

Yêu cầu: Nhập ba số nguyên a, b và c, tính và in ra UCLN của cả ba số.

Cách làm:

• • Tính UCLN của hai số đầu tiên
  • Dùng kết quả đó để tiếp tục tính với số thứ ba
  • Áp dụng thuật toán Euclid để đảm bảo hiệu suất

Dưới đây là ví dụ minh họa:

def gcd(a, b):    while b != 0:        a, b = b, a % b    return a a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) c = int(input(“Nhập c: “)) result = gcd(gcd(a, b), c) print(“UCLN là:”, result)

Giải thích:

• • Hàm gcd(a, b) được dùng để tính UCLN của hai số
  • Áp dụng lồng nhau: gcd(gcd(a, b), c)
  • Kết quả cuối cùng là UCLN của cả ba số

Ví dụ:

• • Nhập a = 12, b = 18, c = 24 → Kết quả: 6
  • Nhập a = 8, b = 16, c = 32 → Kết quả: 8

Bài 3: Rút gọn phân số bằng ước chung lớn nhất

Yêu cầu: Nhập tử số và mẫu số của một phân số, rút gọn phân số đó về dạng tối giản.

Cách làm:

• • Tính UCLN của tử số và mẫu số
  • Chia cả tử và mẫu cho UCLN
  • In ra phân số sau khi rút gọn

Dưới đây là ví dụ minh họa:

from math import gcd tu = int(input(“Nhập tử số: “)) mau = int(input(“Nhập mẫu số: “)) ucln = gcd(tu, mau) tu_rut_gon = tu // ucln mau_rut_gon = mau // ucln print(“Phân số sau khi rút gọn:”, f”{tu_rut_gon}/{mau_rut_gon}”)

Giải thích:

• • Sử dụng hàm gcd() để tìm UCLN của tử và mẫu
  • Chia cả hai cho UCLN để thu được phân số tối giản
  • Kết quả đảm bảo không thể rút gọn thêm

Ví dụ:

• • Nhập 12/18 → Kết quả: 2/3
  • Nhập 20/30 → Kết quả: 2/3

Bài 4: Kiểm tra 2 số có nguyên tố cùng nhau

Yêu cầu: Nhập hai số nguyên a và b, kiểm tra xem chúng có nguyên tố cùng nhau hay không.

Cách làm:

• • Tính UCLN của hai số
  • Nếu UCLN = 1 → hai số nguyên tố cùng nhau
  • Ngược lại → không phải

Dưới đây là ví dụ minh họa:

from math import gcd a = int(input(“Nhập a: “)) b = int(input(“Nhập b: “)) if gcd(a, b) == 1:    print(“Hai số nguyên tố cùng nhau”) else:    print(“Hai số không nguyên tố cùng nhau”)

Giải thích:

• • Sử dụng hàm gcd() để tìm UCLN
  • So sánh kết quả với 1 để đưa ra kết luận

Ví dụ:

• • a = 8, b = 15 → UCLN = 1 → nguyên tố cùng nhau
  • a = 12, b = 18 → UCLN = 6 → không nguyên tố cùng nhau

Qua bài viết, bạn đã nắm được nhiều phương pháp tìm ước chung lớn nhất Python, bao gồm cả cách cơ bản lẫn các thuật toán tối ưu và nâng cao. Việc kết hợp lý thuyết với các ví dụ và bài tập thực hành sẽ giúp bạn hiểu sâu hơn và áp dụng hiệu quả trong các bài toán thực tế. Hy vọng những kiến thức này sẽ giúp bạn tự tin hơn khi xử lý các bài toán liên quan đến UCLN trong Python.

￭ Xem Thêm: TOP 30+ Khóa Học Python TPHCM Chất Lượng & Uy Tín Nhất [UPDATE 2026]