如何求兩個數的最大公因數

求兩個數的最大公因數（Greatest Common Divisor, GCD）可以使用以下幾種方法：

1. 質因數分解法：將兩個數分別分解為質因數的乘積，然後找出共同的質因數，將它們相乘得到最大公因數。

2. 長除法：使用長除法將較大的數除以較小的數，直到商為零，然後將除數的乘積作為最大公因數。

3. 歐幾里得算法（Euclidean algorithm）：這是求兩個整數最大公因數的一種快速算法。基本思想是：gcd(a, b) = gcd(b, a mod b)，也就是說，兩個數a和b的最大公因數等於b和a除以b後的餘數的最大公因數。

以下是一個使用歐幾里得算法求最大公因數的Python示例：

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

# 示例
a = int(input("Enter the first number: "))
b = int(input("Enter the second number: "))
print("The greatest common divisor of", a, "and", b, "is", gcd(a, b))

這個算法時間複雜度為O(log(max(a, b)))，其中a和b是你要尋找最大公因數的兩個數。

如果你需要求任意多個數的最大公因數，可以使用質因數分解法或者將歐幾里得算法應用於多個數。對於多個數的情況，可以使用一個數作為基礎，然後用歐幾里得算法依次求出其他數與這個基礎數的最大公因數。