// 第 1 周 – 算法示例：最大公约数（欧几里得算法）
// 运行：java Gcd.java
public class Gcd {

    // 伪代码：
    //   Function GCD(a, b)
    //     While b ≠ 0
    //       m ← a mod b ; a ← b ; b ← m
    //     End while
    //     Return a
    //   End function
    static int gcd(int a, int b) {
        while (b != 0) {
            int m = a % b;
            a = b;
            b = m;
        }
        return a;
    }

    // 同样的算法，打印每一步 – 便于在黑板上跟踪。
    static int gcdTrace(int a, int b) {
        System.out.printf("%6s %6s %6s%n", "a", "b", "a mod b");
        while (b != 0) {
            int m = a % b;
            System.out.printf("%6d %6d %6d%n", a, b, m);
            a = b;
            b = m;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println("GCD(48, 18) = " + gcd(48, 18));
        System.out.println();
        int r = gcdTrace(1071, 462);
        System.out.println("GCD(1071, 462) = " + r);
    }
}