Danh mục: 34 Học Python – Tìm UCLN của 2 số nguyên dương a

Bài 34: Tìm Ước Chung Lớn Nhất (UCLN) của Hai Số Nguyên Dương a, b bằng Python

Giới Thiệu

Ước chung lớn nhất (UCLN) của hai số nguyên dương a và b là số lớn nhất chia hết cho cả a và b. Bài viết này hướng dẫn cách tìm UCLN bằng Python, bao gồm phương pháp cơ bản và thuật toán Euclid tối ưu.

Ưu Đãi lớn thêm danh sách 10 bài tập python  rèn luyện kỹ năng và nâng cao tay nghề:

1. Bài 26 – Tính Tổng Những Số Chia Hết Cho 3 và 5 bằng Python

2. Bài 27: Kiểm tra số nguyên tố bằng Python (2 cách tối ưu)

3. Bài 28: Tính Tổng Các Số Nguyên Từ m Đến n Bằng Python
4. Bài 29: Đếm Số Chia Hết Cho 3 Từ m Đến n Bằng Python
5. Bài 30 Đếm Số Chia Hết Cho 3 Hoặc 5 Và Tính Tổng Các Số Chẵn Bằng Python
6. Bài 31: Đếm Số Nguyên Tố Trong Khoảng Từ m Đến n Bằng Python
7. Bài 32 : In Các Số Nguyên Tố Từ m Đến n Bằng Python
8. Bài 33: Tính Trung Bình Cộng Các Số Nguyên Tố Từ m Đến n Bằng Python
9. Bài 34: Tìm Ước Chung Lớn Nhất (UCLN) của Hai Số Nguyên Dương a, b bằng Python
10. Bài 35: Rút Gọn Phân Số Bằng Python

Phương Pháp Tìm UCLN

Có hai phương pháp chính để tìm UCLN:

1. Phương pháp cơ bản: Duyệt tất cả các số từ 1 đến min(a, b) để tìm ước chung lớn nhất.
2. Thuật toán Euclid: Dùng phép chia liên tiếp để tìm UCLN nhanh hơn.

Viết Chương Trình Python

1. Phương Pháp Cơ Bản

# Hàm tìm UCLN theo phương pháp duyệt
def ucln_brute_force(a, b):
    ucln = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            ucln = i
    return ucln
# Nhập giá trị a và b từ người dùng
a = int(input("Nhập số nguyên dương a: "))
b = int(input("Nhập số nguyên dương b: "))
# Kiểm tra điều kiện đầu vào
if a <= 0 or b <= 0:
    print("Vui lòng nhập hai số nguyên dương.")
else:
    print(f"Ước chung lớn nhất của {a} và {b} là: {ucln_brute_force(a, b)}")

2. Thuật Toán Euclid (Tối Ưu)

# Hàm tìm UCLN bằng thuật toán Euclid
def ucln_euclid(a, b):
    while b:
        a, b = b, a % b
    return a
# Nhập giá trị a và b từ người dùng
a = int(input("Nhập số nguyên dương a: "))
b = int(input("Nhập số nguyên dương b: "))
# Kiểm tra điều kiện đầu vào
if a <= 0 or b <= 0:
    print("Vui lòng nhập hai số nguyên dương.")
else:
    print(f"Ước chung lớn nhất của {a} và {b} là: {ucln_euclid(a, b)}")

So Sánh Hai Phương Pháp

Thuật toán Euclid hiệu quả hơn nhiều so với phương pháp duyệt thông thường.

Ứng Dụng Của UCLN

• Rút gọn phân số.
• Giải phương trình Diophantine.
• Xử lý số học trong lập trình.

Kết Luận

Việc tìm UCLN là một bài toán quan trọng trong toán học và lập trình. Phương pháp Euclid giúp tính UCLN nhanh chóng ngay cả với số lớn. Hãy sử dụng thuật toán này để tối ưu chương trình của bạn!

Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !

Khóa học Python online từ cơ bản đến nâng cao