求最大公约数（gcd）的一点心得

摘要：
最大公约数的一些心得。

求两个数的最大公约数

在《算法 第4版》中，给出迭代求最大公约数的示例：

• Java

public static int gcd(int p, int q) {
    if (q == 0) return p;
    int r = p % q;
    return gcd(q, r);
}

可以注意到，这里用到了迭代的思想。两数相除，再拿被除数除余数，如此辗转，直到余数为零，返回此时的被除数 。
上述代码可简化为：

• Java

public static int gcd(int p, int q) {
    return q == 0 ? p : gcd(q, p % q);
}

另一个非迭代版本：

• Java

public static int gcd(int x, int y) {
     while (y != 0) { 
         int temp = y;
         y = x % y; // 余数变被除数
         x = temp; //被除数变除数
     }
     return x;
 }

n个数求最大公约数

一个常见的求法就是设置一个初始的 $gcd$，求它和第一个数的 $gcd$。再将该 $gcd$ 和第二个数求它们的 $gcd$，如此辗转，直到求第 $n$ 个数和前 $n-1$ 个数的 $gcd$。
复杂度是 $O(N)$。

• Java

class GcdN {
    public static int gcdN (int[] arr) {
        int gcd = arr[0];
        for(int each : arr) 
            gcd = gcd(gcd, each);
        return gcd;
    }
    private static int gcd(int p, int q) {
        return q == 0 ? p : gcd(q, p % q);
    }
}