Как написать функцию Java для реализации алгоритма Евклида для вычисления наибольшего общего делителя gcd (m, n)

Мне нужно отредактировать основную функцию, чтобы вычислить (m,n) для всех m и n от 2 до 10, но я не знаю, как это сделать.

Мне нужно написать функцию Java для реализации алгоритма Евклида для вычисления наибольшего общего делителя gcd(m, n), который является наибольшим целым числом k, делящим и m, и n.

Когда цикл останавливается, НОД находится в m. Добавьте функцию gcd() в класс NumericFunctions и включите код в main() для вычисления gcd(m, n) для всех m и n от 2 до 10.

Исходный код:

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(" ");


            }
      }

java function algorithm greatest-common-divisor
person Coding Noob    schedule 29.08.2016    source источник
comment
Что происходит, когда вы запускаете этот код? Чем результат отличается от желаемого?   -  person Code-Apprentice    schedule 29.08.2016
comment
Возможный дубликат Как найти GCD, LCM в наборе чисел   -  person DimaSan    schedule 29.08.2016
comment
Код, который вы дали, похоже, делает именно то, что вы хотите. Он вычисляет НОД всех пар чисел от 1 до 10. Так в чем проблема?   -  person Code-Apprentice    schedule 29.08.2016

Ответы (1)


arrow_upward
2
arrow_downward

В вашей функции 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));
        }
    }
}
person tnas    schedule 29.08.2016