Hệ số chung cao nhất của Python (HCF / GCD)

Tính ước số chung lớn nhất (HCF) hoặc ước số chung lớn nhất (GCD) của hai số bằng thuật toán Euclide.

Tổng quan

Hệ số chung cao nhất (HCF), còn được gọi là Ước chung lớn nhất (GCD), là số nguyên dương lớn nhất chia hai hoặc nhiều số nguyên mà không để lại số dư.

Thuật toán Euclide là một phương pháp cực kỳ hiệu quả để tính toán HCF. Nó phát biểu rằng GCD của hai số cũng chia hết hiệu của chúng.

Trong Python, chúng tôi triển khai điều này lặp đi lặp lại bằng cách sử dụng vòng lặp while trong đó chúng tôi liên tục thay thế số lớn hơn bằng phần còn lại của phép chia của chúng.

Đầu ra mã & thực thi

Thực hiện vòng lặp Euclide để tìm HCF/GCD của hai số.

hcf_gcd.py

Thử trong Trình chỉnh sửa

def find_gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b
    return a

print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))

Đầu ra thiết bị đầu cuối

GCD of 36 and 60 is: 12
GCD of 17 and 5 is:  1

Triển khai từng bước

Đơn giản hóa phân số và công cụ toán học
Các thuật toán mã hóa (như tạo khóa riêng RSA)
Thiết kế lịch sự kiện định kỳ

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

Python có chức năng GCD tích hợp không?

Vâng! Thư viện chuẩn của Python chứa `math.gcd(a, b)` sử dụng triển khai C được biên dịch bên trong.

Chủ đề liên quan

Bội số chung thấp nhất của Python (LCM)

Tìm bội chung nhỏ nhất (LCM) của hai số bằng cách sử dụng mối quan hệ HCF của chúng trong Python.

Tập lệnh máy tính đơn giản Python

Xây dựng một máy tính cơ bản bằng Python. Tìm hiểu cách ánh xạ các toán tử toán học, thực hiện các luồng thực thi của người dùng và xử lý logic nguyên bản.