辗转相除法，又名背后的花瓣算法，用于求两个数 a , b 的最大公约数(最大公因子)，表达式为 gcd(a, b) = gcd(b, a % b) ，其中 gcd 是 Great Common Divisor (最大公约数) 的缩写。
使用过程
关键就是理解 gcd(a, b) = gcd(b, a % b) 这个等式，即 a, b 的最大公约数等于 b 与 a / b 余数 的最大公约数相等。
直接举个例子，方便我们更好地理解与使用这个式子。例如我们求（1112，695）这两个数的最大公约数，步骤如下：
1112 % 695 = 417
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0
以上步骤相当于：gcd(1112, 695) = gcd（695, 1112 % 695 = 417）= gcd（417, 695 % 417 = 278）= gcd（278, 417 % 278 = 139）= 0，当等式结果为 0 时，上一个式子的余数就是我们所要的最大公约数，也就是（1112，695）的最大公约数为 139 。
代码实现 #include <stdio.h>int gcd(int a, int b){int tmp = 0;/*使用if语句确保a为较大值，b为较小值，这样函数就对输入无大小顺序的要求*/if(a<b){tmp = a;a = b;b = tmp;}/*gcd(a, b) = gcd(b, a % b)当 a % b == 0 时，b 为所求的最大公约数*/while(a % b != 0){ tmp = a;a = b;b = tmp % b;}return b;}
