欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则
d|b , d|r ，但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等

怎么好象这些算法要自己想出来的么?我还以为先求出两个数的约数,再选出共同的最大数呢...晕死..

在这里谢谢大家的解答了

我发一个好理解的，别见笑！
#include<stdio.h>
int main(void)
{
 int m,n,i,t;
 scanf("%d %d",&m,&n);
 for(i=2;i<=m&&i<=n;i++)
  {
    if(m%i==0&&n%i==0)
    t=i;
  }
 printf("t=%d\n",t);
 system("pause");
 retrun 0;
}

求最大公约数还是展转求余法好呀 欧几里德算法  方便

#include<stdio.h>
int main()
{int i,n,m;
scanf("%d%d",&n,&m);
for(i=n;i>0;i--)
{if(n%i==0&&m%i==0)
break;}
printf("最大公约数：%d",i);
}

有错吧。没有最大公约数的情况没考虑。