最大公因數 (Greatest Common Divisor)

最大公因數 教學與筆記。

說明

使用輾轉相除法求最大公因數。

• 非遞迴 (Non Recursive)

  #include <stdio.h>
  
  int gcd(int x, int y) {
      int mod = 0;
  
      while(y != 0) {
          mod = x % y;
          x = y;
          y = mod;
      }		
      return x;
  }
  
  int main() {
      printf("%d\n", gcd(54, 24)); // 6
  }

• 遞迴 (Recursive)

  #include <stdio.h>
  
  int gcd(int x, int y) {
      if (y == 0)
          return x;
      return gcd(y, x % y);
  }
  
  int main() {
      printf("%d\n", gcd(54, 24)); // 6
  }