什么是辗转相除法？
辗转相除法（又名欧几里德算法），它主要用于求两个正整数的最大公约数。是已知的最古老的算法。
用辗转相除法求132和72的最大公约数的步骤：
132 / 72 = 1 ... 60
72 / 60 = 1 ... 12
60 / 12 = 5
所以他们的最大公约数就是12。
如何实现辗转相除法？
我们把要求的两个数定为a和b（a > b）。
首先算1.a / b = c ... r
接着2.a = b, b = r，并判断r是否是0。若不为零则重复1，若为0则输出除数，也就是b。
但是，仔细一想，b = r，r = 0，输出的结果总是0，所以我们要找到原来的b，就是a，所以正确的应该是输出a。
这是经过重复修改后的伪代码：
while（b ≠ 0）{
r = a mod b;
a = b;
b = r;
if(r == 0) break and show a;
}
完整的程序代码：
#include <stdio.h>
#include <stdlib.h> int fun(int, int); int main(int argc,char *argv[])
{
int a,b,n;
printf("请输入两个数：");
scanf("%d%d",&a,&b);
if( (a <= ) || (b <= ) ){ //数据检查
printf("除数不能为0");
return ;}
n = ( a > b ? fun(a,b) : fun(b,a) ); //调用函数并处理大小顺序
printf("最大公因数：%d",n);
getch();
return ;
} int fun(int a,int b)
{
int r;
while(b){ //因为b的初值不为0，所以循环有效。当b=0时，余数r=0，循环终止。
r = a % b; //取余数
a = b; //除数作被除数
b = r; //商作除数
}
return a; //a就是最后的除数
}