如何查找分子和分母的最大公約數

查找分子和分母的最大公約數（Greatest Common Divisor, GCD）可以使用以下幾種方法：

  1. 質因數分解法：將分子和分母分解為質因數，然後找出共同的質因數，將它們相乘得到最大公約數。

  2. 長除法：將分子除以分母，得到一個餘數。如果餘數不是0，將分母除以餘數，得到一個新的餘數。重複這個過程，直到餘數為0。最後，將所有的除數相乘得到最大公約數。

  3. 歐幾里得算法（Euclidean algorithm）：這是最常用的方法之一，它的基本思想是：如果a是b的倍數，那麼a和b的最大公約數就是b；如果a不是b的倍數，那麼最大公約數就是a和b中較小的數a和b-a的最大公約數。

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

假設我們要找出24和36的最大公約數。

  1. 開始時，我們設a = 24，b = 36。
  2. 因為b > a，我們將a賦值給b，將b賦值給a - b（即餘數）。
  3. 我們得到新的a = 36 - 24 = 12，新的b = 24。
  4. 因為b > a，我們再次將a賦值給b，將b賦值給a - b。
  5. 我們得到新的a = 24 - 12 = 12，新的b = 12。
  6. 因為a = b，我們停止運算。
  7. 最大公約數就是a或b，即12。

這就是歐幾里得算法的基本運行過程。在實際應用中，我們可以使用迴圈來實現這個算法，直到a和b相等為止。