Java 如何求最大公约数(GCD)

求最大公约数 (GCD)

最大公约数 (GCD) 是能同时整除两个数的最大整数。

int a = 36;
int b = 60;
int gcd = 1;

for (int i = 1; i <= a && i <= b; i++) {
  if (a % i == 0 && b % i == 0) {
    gcd = i;
  }
}

System.out.println("GCD: " + gcd);

说明:

我们想要找到能同时整除 36 和 60 的最大整数。

• 循环从 1 开始，一直循环到较小的整数 (36)。
• 在每一步，我们检查 i 是否能整除这两个数(使用 %，即取余运算符)。
• 如果能，我们就将 gcd 更新为该值。

例如:

• 36 % 12 == 0 和 60 % 12 == 0，所以 12 是这两个数的约数。
• 之后，循环找到 gcd = 12 作为最大公约数。

因此程序输出 GCD: 12。