题目

辗转相除法手写过程逐步打印

思路

在 GCD 循环里每步 System.out 当前 a,b 与 a%b；直到余数 0，最后一非零除数即 GCD，也可逐步打印商。

解题分析

本题重点是展示辗转相除每一步的商和余数，算法与第 23 题相同，多的是格式化输出，便于对照手算。

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int a = 48, b = 18;
        int x = a, y = b;
        while (y != 0) {
            System.out.println(x + " / " + y + " = " + (x / y) + " ... " + (x % y));
            int t = x % y; x = y; y = t;
        }
        System.out.println("gcd = " + x);
    }
}

运行示例

输出：

48 / 18 = 2 ... 12
18 / 12 = 1 ... 6
12 / 6 = 2 ... 0
gcd = 6