如何编写一个实现欧几里德算法的函数来计算最大公约数(m,n)

Question

我试图将gcd()函数添加到NumericFunctions类中，并在main中包含代码来计算gcd(m,n)。

但是，我一直得到一个错误:

Exception in thread "main" java.lang.StackOverflowError
    at NumericFunctions.gcd(NumericFunctions.java:14)

源代码:

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(" ");
               System.out.println(factorial(n));
            }
      }
}

Answer 1

检查gcd()方法中的以下更正:

public static int gcd (int n, int m) {
    if ((n % m) == 0)
        return m; // <-- first correction
    else
        return gcd(m, n % m);  // <-- second correction
}