如何编写一个简单的Java程序,找到两个数字之间最大的公约数？

Question

这是一个问题:

"编写一个名为gcd的方法,它接受两个整数作为参数,并返回两个数字的最大公约数.两个整数a和b的最大公约数(GCD)是a和b两者的最大整数.任何数字和1的GCD是1,任何数字的GCD和0都是该数字.

计算两个数字的GCD的一种有效方法是使用Euclid算法,该算法表明以下内容:

GCD(A, B) = GCD(B, A % B) 
GCD(A, 0) = Absolute value of A"

我真的很困惑如何解决这个问题.我只想提供一些提示和提示,告诉我到目前为止我在程序中做错了什么.(我必须放入扫描仪,这是我老师的要求.)不要给我一个完整的代码,因为我有点想自己解决这个问题.也许只是给我一个暗示我如何结合你在上面看到的这个公式.(如果你想知道为什么我输入== 0,那是因为我认为如果你有两个数字,比如0和90,他们的GCD会是0吗？)

此外,我的代码必须包括while循环......如果循环我会更喜欢...

提前致谢!:)

我目前的计划:

public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        int a = console.nextInt();
        int b = console.nextInt();
        gcd (a, b);
    }

    public static void gcd(int a, int b) {
        System.out.print("Type in two numbers and I will print outs its Greatest Common Divisor: ");
        int gcdNum1 = console.nextInt();
        int gcdNum2 = console.nextInt();
        while (gcdNum1 == 0) {
            gcdNum1 = 0;
        }
        while (gcdNum2 > gcdNum1) {
            int gcd = gcdNum1 % gcdNum2;
        }
        System.out.print(gcdNum1 + gcdNum2);
    }
}

Answer 1

递归方法是:

static int gcd(int a, int b)
{
  if(a == 0 || b == 0) return a+b; // base case
  return gcd(b,a%b);
}

使用while循环:

static int gcd(int a, int b)
{
  while(a!=0 && b!=0) // until either one of them is 0
  {
     int c = b;
     b = a%b;
     a = c;
  }
  return a+b; // either one is 0, so return the non-zero value
}

当我返回时a+b,我实际上返回非零数字,假设其中一个为0.

Answer 2

您也可以使用三行方法:

public static int gcd(int x, int y){
  return (y == 0) ? x : gcd(y, x % y);
}

这里,如果y = 0,则返回x.否则,将gcd使用不同的参数值再次调用该方法.