Danh mục: 86 Học Python – Viết hàm tìm UCLN mới nhất

Bài 86: Viết hàm tìm Ước Chung Lớn Nhất (UCLN) trong Python

Giới Thiệu

Ước chung lớn nhất (UCLN) của hai số nguyên dương là số nguyên dương lớn nhất chia hết cho cả hai số đó. Bài viết này hướng dẫn hai cách viết một hàm Python để tìm UCLN của hai số nguyên dương: cách thông thường và cách tối ưu hóa sử dụng thư viện có sẵn.

Khuyến mãi đặc biệt thêm danh sách 10 bài tập nâng cao khả năng lập trình Python:

1. Bài 81: Đếm số ký tự thường trong xâu bằng Python
2. Bài 82: Tìm tên của một người trong chuỗi họ và tên bằng Python
3. Bài 83 Tìm họ và chữ lót của một người từ chuỗi họ và tên bằng Python
4. Bài 84: Tính chu vi và diện tích của tam giác có sử dụng hàm trong Python
5. Bài 85: Viết hàm kiểm tra chia hết cho 5 trong Python
6. Bài 86: Viết hàm tìm Ước Chung Lớn Nhất (UCLN) trong Python
7. Bài 87: Viết hàm tính giai thừa n! trong Python
8. Bài 88: Viết hàm P(x, n) để tính giá trị x^n trong Python
9. Bài 89: Vẽ hình chữ nhật bằng dấu * trong Python
10. Bài 90: Sử dụng hàm lồng nhau trong Python

Cách Thực Hiện

Cách 1: Sử dụng thuật toán Euclid (Cách thông thường)

1. Dùng phép chia liên tục để tìm UCLN.
2. Lặp lại cho đến khi phần dư bằng 0.
3. Trả về số cuối cùng là UCLN.

def tim_ucln_thuong(a, b):

    while b != 0:

        a, b = b, a % b

    return a

Cách 2: Sử dụng thư viện math (Cách tối ưu hóa)

Python cung cấp hàm math.gcd() giúp tính UCLN nhanh chóng và tối ưu hơn.

import math
def tim_ucln_toi_uu(a, b):
    return math.gcd(a, b)
Chương Trình Hoàn Chỉnh
import math
def tim_ucln_thuong(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def tim_ucln_toi_uu(a, b):
    return math.gcd(a, b)
# Nhập hai số nguyên 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 và hiển thị kết quả
if a > 0 and b > 0:
    print(f"UCLN theo cách thường của {a} và {b} là: {tim_ucln_thuong(a, b)}")
    print(f"UCLN theo cách tối ưu của {a} và {b} là: {tim_ucln_toi_uu(a, b)}")
else:
    print("Vui lòng nhập hai số nguyên dương hợp lệ.")

Ví Dụ Chạy Chương Trình

Nhập số nguyên dương a: 56

Nhập số nguyên dương b: 98

UCLN theo cách thường của 56 và 98 là: 14

UCLN theo cách tối ưu của 56 và 98 là: 14

So Sánh Hai Cách

Kết Luận

Cả hai cách đều cho kết quả chính xác. Nếu bạn muốn hiểu rõ thuật toán, hãy sử dụng cách 1. Nếu muốn viết mã nhanh và tối ưu hơn, hãy sử dụng math.gcd(). Hy vọng bài viết hữu ích cho bạn!