Java第23题：求两个正整数的最大公约数（欧几里得算法）

题目

求两个正整数的最大公约数（欧几里得算法）

思路

本题用欧几里得算法求两个正整数的最大公约数 GCD。 循环 while (b)：每次用余数更新 t=a%b; a=b; b=t，直到 b 为 0，此时 a 就是 GCD。题目保证正整数时可不必先交换大小。

解题分析

欧几里得算法反复用余数缩小问题：gcd(a,b)=gcd(b,a mod b)，直到余数为 0。辗转相除的 while 写法与手算一致；递归写法代码更短，层数在 log 量级内一般没问题。

完整程序

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) {
            int t = x % y;
            x = y;
            y = t;
        }
        System.out.println(x);
    }
}

运行示例

输出：

6