C语言：三种方法求最大公约数

本文将介绍三种使用C语言求两个整数最大公约数的方法，并提供代码示例。

1. 辗转相除法（欧几里德算法）

辗转相除法是求最大公约数的经典算法，其原理是：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

以下是使用辗转相除法求最大公约数的C程序：

#include <stdio.h>

int gcd(int a, int b) {
    int remainder;
    
    while (b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }
    
    return a;
}

int main() {
    int num1, num2;
    
    printf('请输入两个整数：');
    scanf('%d %d', &num1, &num2);
    
    int result = gcd(num1, num2);
    
    printf('GCD=%d\n', result);
    
    return 0;
}

输入格式:

'%d%d'

输出格式:

'GCD=%d\n'

输入样例:

36 8

输出样例:

GCD=4

2. 更相减损法

更相减损法是另一种求最大公约数的算法，其原理是：两个正整数的最大公约数等于其中较小的数和两数之差的最大公约数。

#include <stdio.h>

int gcd(int a, int b) {
  while (a != b) {
    if (a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  return a;
}

int main() {
  int num1, num2;

  printf('请输入两个整数：');
  scanf('%d %d', &num1, &num2);

  int result = gcd(num1, num2);

  printf('GCD=%d\n', result);

  return 0;
}

3. 递归法

递归法可以简洁地实现辗转相除法，其代码如下：

#include <stdio.h>

int gcd(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

int main() {
  int num1, num2;

  printf('请输入两个整数：');
  scanf('%d %d', &num1, &num2);

  int result = gcd(num1, num2);

  printf('GCD=%d\n', result);

  return 0;
}

以上是三种求最大公约数的C语言实现方法，您可以根据实际情况选择合适的方法。