最大公約數・最小公倍數計算器
輸入兩個正整數後，用輾轉相除法（歐幾里得演算法）求出最大公約數（GCD），並逐步顯示計算過程。同時計算出最小公倍數（LCM）。
| 最大公約數（GCD） | |
|---|---|
| 最小公倍數（LCM） |
輾轉相除法的計算過程
| 計算式 |
|---|
| = × + |
什麼是輾轉相除法（歐幾里得演算法）
輾轉相除法是求兩個整數最大公約數的經典演算法。其步驟是："關注較大數除以較小數所得的餘數，用除數和餘數這一組數重複相同的操作，當餘數變為0時，此時的除數即為最大公約數"。即使是很大的數，也能通過較少的步驟準確求出最大公約數。這一方法記載於西元前300年左右歐幾里得所著的《幾何原本》中，被認為是現存最古老的演算法之一。
使用提示
- 最小公倍數（LCM）可以用"A×B÷最大公約數（GCD）"這一公式求出。常用於分數通分，或求多個週期不同的日程何時會重合。
- 如果兩個數互質（最大公約數為1），那麼最小公倍數就直接等於A×B。
- 輾轉相除法的一個實用優點是：即使是求較大數字之間的最大公約數，它也比先做質因數分解再求解要快。
- 輸入的兩個數字的大小順序不影響結果，程式內部會自動從較大的數開始計算。
常見問題
最大公約數是"能同時整除兩個數的整數中最大的一個"，最小公倍數是"兩個數的倍數中最小的一個"。例如12和18，最大公約數是6，最小公倍數是36。
通過質因數分解求最大公約數的方法，數字越大質因數分解本身就越耗時；而輾轉相除法只需反覆進行除法和求餘運算，因此即使是位數很大的整數，也能快速求出最大公約數。
本工具僅支援正整數。如果輸入0、負數或小數，將不會顯示計算結果。
本工具支援兩個數字的計算。如果是3個及以上，可以兩兩依次計算（例如先求A和B的最大公約數，再求該結果與C的最大公約數）來得到同樣的結果。
閒話 ― 為什麼一個2000多年前的演算法至今仍在使用
輾轉相除法記載於西元前300年左右古希臘數學家歐幾里得所著的數學著作《幾何原本》（Elements）第七卷中。它被認為是現存記錄中最古老的演算法之一，即便過去了2000多年，如今依然是電腦科學教材中最先介紹的代表性演算法之一。
這一演算法之所以能沿用至今，關鍵在於其計算效率之高。數學上已證明，輾轉相除法所需的步數大致與輸入數字的位數成正比（最壞情況出現在與斐波那契數列相關的數字組合中），因此無論數字多大，都能在現實可行的時間內求出最大公約數。
現代密碼技術（如RSA加密）在金鑰生成過程中，仍然會用到最大公約數的計算（或其擴充套件版本——擴充套件歐幾里得演算法）。古代的數學發現如今支撐著網際網路安全的基礎技術之一，這一事實生動地展示了數學的普適性。