辗转相除求最大公约数的算法
已知a/b=cr(a、b、c、r都是整数)
假设d是a的余数，d也是b的余数，那么d是a和b的公约数
d是a和b的约数，a和b是d的倍数，B * C也是d的倍数
既然a和B*C都是d的倍数，那么a和B*C之差也是d的倍数
A - B*C=R
所以r也是d的倍数
如果d是a或b的公约数，d也是b和r的公约数
因此，(a，b )=(b，r ) )。
根据以上证明可以求出最大的公约数
例如，求出72和28最大公约数
72/28=2
28/16=1 12
16/12=1 4
12/4=3 0
可以看出72和28的最大公约数是4
1 #包含
2输入主()。
3 int a； //除数
4 int b； //被除数
5 int r=1； //馀数，代入初始值为1
6 printf ('输入除数和被除数(用空格分开) )；
7scanf('%d%d )，a，b )；
8while(r=0() /如果a
9 r=a % b；
10 a=b；
11 b=r；
12 }
13 printf (最大公约数为%d(n )，a )； //此时b的值已经进入了a，所以输出的a是最大公约数
14返回0；
15 }