利用辗转相除法求两个整数的最大公约数

    在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。两个整数的最大公约数(亦称公因子)是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。具体的介绍请看维基百科中的解释——辗转相除法。下面是具体实现代码：

/* (1) 利用递归实现 */
int rgcd(int p, int q) {
    if (q == 0) 
        return p;
    int r = p%q;
    return gcd(q, r);
}
/* (2) 利用迭代实现 */
int gcd(int p, int q) {
    int temp;
    while (q != 0) {
        int temp = p%q;
        p = q;
        q = temp;
    }

    return p;
}