最大公約數計算機

最大公約數（Greatest Common Divisor，GCD）計算機是一種用來找出兩個或更多整數的最大公約數的算法。在數學中，最大公約數是指兩個或更多整數的共有因子中最大的那一個。

在計算機科學中，有許多算法可以用來計算最大公約數，其中最著名的是埃拉托斯特尼篩法（Eratosthenes' sieve）和更高效的更相剋除法（輾轉相除法，Extended Euclidean algorithm）。

以下是一個簡單的Python程式，它使用更相剋除法來計算兩個整數的最大公約數：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 使用示例
num1 = int(input("請輸入第一個數："))
num2 = int(input("請輸入第二個數："))
print("最大公約數是：", gcd(num1, num2))

這個程式首先要求用戶輸入兩個整數，然後使用gcd函式來計算它們的最大公約數並列印出來。

更相剋除法的基本思想是，如果我們要找出兩個數字a和b的最大公約數，我們可以不斷地用較小的數字b去除a，直到b為0為止。此時，a就是a和b的最大公約數。

這個算法的時間複雜度為O(log(max(a, b)))，其中max(a, b)是a和b中的最大值。這個算法在實際應用中非常高效，可以快速地找出兩個數字的最大公約數。