如何编写 Java 函数来实现欧几里得算法计算最大公约数 gcd(m, n)

Question

我需要编辑主函数来为 2 到 10 之间的所有 m 和 n 计算 (m,n)，但我不确定该怎么做。

我需要写一个Java函数来实现欧几里德算法来计算最大公约数gcd(m, n)，它是除以m和n的最大整数k。

当循环停止时，gcd在m。将 gcd() 函数添加到 NumericFunctions class 并在 main() 中包含代码以计算 2 到 10 之间的所有 m 和 n 的 gcd(m, n)。

源代码：

public class NumericFunctions {

   public static long factorial(int n) {

      long result = 1;

      for (int i = 2; i <= n; i++) {

         result *= i;
      }
      return result;
   }

   public static int gcd (int n, int m) {

      if ((m % n) == 0) 

         return n;

      else

         return gcd(n, m % n);
}

     public static void main(String[] args) {

         for (int n = 1; n <= 10; n++)

            for (int m = 1; m <= 10; m++){

               System.out.println(gcd(n,m));

               System.out.println(" ");


            }
      }

Answer 1

您的 gcd() 函数中存在无限递归（例如 gcd(2, 1);）。所以，把你的功能改成这样

public static int gcd (int n, int m) {

    if (m > n) {
      if ((m % n) == 0) 
         return n;
      else
         return gcd(n, m % n);
    }
    else {
        if ((n % m) == 0) 
             return m;
          else
             return gcd(m, n % m);
    }
}

public static void main(String[] args) {    

    for (int n = 1; n <= 10; n++) {

        for (int m = 1; m <= 10; m++) {
            System.out.println("n: " + n + " m: " + m + " gcd: " + gcd(n, m));
        }
    }
}

如何编写 Java 函数来实现欧几里得算法计算最大公约数 gcd(m, n)

How to write a Java function to implement Euclid's algorithm for computing the greatest common divisor gcd(m, n)

java

algorithm

function

greatest-common-divisor