Java 求两个数的 GCD

 Java 常见例子

GCD 代表最大公约数。两个数的 GCD 是能整除这两个数的最大数。

例如 - 20 和 25 的 GCD 是 5，50 和 100 的 GCD 是 50。

方法1:使用For循环求两个数字的GCD

在下面的例子中，for循环用于将变量i从0迭代到较小的数字。如果两个数字都可以被 i 整除，则它会修改 GCD，并最终给出两个数字的 GCD。

public class MyClass {
  public static void main(String[] args) {
    int x = 50;
    int y = 100;
    int gcd = 1;
    int temp;

    if (x > y) {
      temp = x;
      x = y;
      y = temp;
    }

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

    System.out.println("GCD of "+ x +" and "+ y +" is: "+ gcd);
  }
} 

上面的代码将给出以下输出:

GCD of 50 and 100 is: 50 

方法二:使用While循环求两个数的GCD

在下面的例子中，较大的数被替换为一个大数减去较小数的数数字。继续该过程，直到两个数字相等，这将是两个数字的 GCD。

public class MyClass {
  public static void main(String[] args) {
    int p, q, x, y;
    p = x = 20;
    q = y = 25;

    while (x != y) {
      if (x > y)
        x = x - y;
      else
        y = y - x;
    }

    System.out.println("GCD of "+ p +" and "+ q +" is: "+ x);
  }
} 

上面的代码将给出以下输出:

GCD of 20 and 25 is: 5 

方法3:使用递归函数求两个数字的GCD

In下面的例子，使用了递归函数。在此方法中，不使用减法运算符（如上例所示），而是使用模运算符。此方法也称为欧几里得算法。

public class MyClass {
  static int gcd(int x, int y) {
    if (y == 0)
      return x;
    return gcd(y, x%y);  
  }

  public static void main(String[] args) {
    int x = 250;
    int y = 475;

    System.out.println("GCD of "+ x +" and "+ y +" is: "+ gcd(x,y));
  }
} 

上面的代码将给出以下输出:

GCD of 250 and 475 is: 25