原文： https://beginnersbook.com/2018/09/java-program-to-find-gcd-of-two-numbers/

两个数字的 GCD（最大公约数）是最大的正整数，它将两个数字整除而不留任何余数。例如。 30 和 45 的 GCD 是 15。GCD 也称为 HCF（最高公因子）。在教程中，我们将编写几个不同的 Java 程序来找出两个数字的 GCD。

如何在纸上找出 GCD？

为了找出两个数字的 GCD，我们将公因子乘以如下图所示：

Java 程序：查找两个数字的 GCD - 图1

示例 1：使用for循环查找两个数字的 GCD

在这个例子中，我们使用for循环找到两个给定数字的 GCD。

我们正在运行一个 for 循环，从 1 到较小的数字和内部循环，我们将这两个数字除以循环计数器i，范围从 1 到较小的数字值。如果i的值除以两个数字而没有余数，那么我们将该值赋给变量gcd。在循环结束时，变量gcd将具有最大数字，该数字除以两个数字而没有余数。

  1. public class GCDExample1 {
  3.     public static void main(String[] args) {
  5.         //Lets take two numbers 55 and 121 and find their GCD
  6.         int num1 = 55, num2 = 121, gcd = 1;
  8.         /* loop is running from 1 to the smallest of both numbers
  9.          * In this example the loop will run from 1 to 55 because 55
  10.          * is the smaller number. All the numbers from 1 to 55 will be 
  11.          * checked. A number that perfectly divides both numbers would
  12.          * be stored in variable "gcd". By doing this, at the end, the 
  13.          * variable gcd will have the largest number that divides both
  14.          * numbers without remainder.
  15.          */
  16.         for(int i = 1; i <= num1 && i <= num2; i++)
  17.         {
  18.             if(num1%i==0 && num2%i==0)
  19.                 gcd = i;
  20.         }
  22.         System.out.printf("GCD of %d and %d is: %d", num1, num2, gcd);
  23.     }
  25. }

输出：

  1. GCD of 55 and 121 is: 11

示例 2：使用while循环查找两个数字的 GCD

让我们使用while循环编写相同的程序。在这里，我们采用不同的方法来寻找 gcd。在这个程序中，我们从较大的数字中减去较小的数字，直到它们变得相同。在循环结束时，数字的值将相同，并且该值将是这些数字的 GCD。

  1. public class GCDExample2 {
  3.     public static void main(String[] args) {
  5.         int num1 = 55, num2 = 121;
  7.         while (num1 != num2) {
  8.             if(num1 > num2)
  9.                 num1 = num1 - num2;
  10.             else
  11.                 num2 = num2 - num1;
  12.         }
  14.         System.out.printf("GCD of given numbers is: %d", num2);
  15.     }
  17. }

输出：

  1. GCD of given numbers is: 11

示例 3：查找两个输入（由用户输入）数字的 GCD

在这个例子中，我们使用Scanner来从用户获取输入。用户将输入两个数字的值，程序将找到这些输入数字的 GCD。

  1. import java.util.Scanner;
  2. public class GCDExample3 {
  4.     public static void main(String[] args) {
  6.         int num1, num2;
  8.         //Reading the input numbers
  9.         Scanner scanner = new Scanner(System.in);
  10.         System.out.print("Enter first number:");
  11.         num1 = (int)scanner.nextInt();
  13.         System.out.print("Enter second number:");
  14.         num2 = (int)scanner.nextInt();
  16.         //closing the scanner to avoid memory leaks
  17.         scanner.close();
  18.         while (num1 != num2) {
  19.             if(num1 > num2)
  20.                 num1 = num1 - num2;
  21.             else
  22.                 num2 = num2 - num1;
  23.         }
  25.         //displaying the result
  26.         System.out.printf("GCD of given numbers is: %d", num2);
  27.     }
  29. }

输出：

  1. Enter first number:30
  2. Enter second number:250
  3. GCD of given numbers is: 10

下面是几个相关的 java 例子：

  1. Java 程序：找到 factorial 数
  2. Java 程序：显示 Fibonacci 系列
  3. Java 程序：找到三个数字中最大的数字