代码递归实现：

int gcd(int a, int b) {  return b ? gcd(b, a%b) : a;}

代码循环实现：

int gcd(int a, int b) {  int temp;  while (b) {    temp = a;        a = b;    b = temp%b;  }  return a;}

2、欧几里德的拓展

我们知道，在数学中，对于任意两个正整数a和b，必定存在一对整数s、t使得sa+tb = gcd(a,b)void exgcd(int a, int b, int * s, int * t) {  if (b == 0) {    *s = 1, *t = 0;  }else {    int next_s, next_t;    exgcd(b, a%b, &next_s, &next_t);    *s = next_t, *t = next_s - a/b * next_t;  }}

当b == 0时可取s = 1, t = 0; 当b != 0时s = next_t, s = next_s - a/b * next_t（即s，t与下一层的s, t存在的关系）;