Question

Даны N натуральных чисел. Найти их наибольший делитель, используя алгоритм Евклида и учитывая, что НОД (a, b, c) = НОД ( НОД (a, b), c). (Написать функцию для расчёта наибольшего общего делителя двух натуральных чисел, используя алгоритм Евклида). Java

Answer 1

Відповідь:

public static long NOD(long a,long b){

   while(a*b!=0){

   if(a>b) a%=b;

   else b%=a;}

   return a+b;}

   public static void main(String[] args){

   long a,b,c;

   Scanner scanner = new Scanner(System.in);

   System.out.println("Введите первое число:");

   a=scanner.nextLong();

   System.out.println("Введите второе число:");

   b=scanner.nextLong();

   System.out.println("Введите третье число:");

   c=scanner.nextLong();

   scanner.close();

   System.out.println("НОД чисел "+a+", "+b+", "+c+" равен "+NOD(NOD(a,b),c));

   }

Пояснення:

Перед выполнением не забудьте подключить Scanner командой import java.util.Scanner;

Answer 2

Вот пример написания функции на Java для расчета наибольшего общего делителя двух натуральных чисел, используя алгоритм Евклида:

public class EuclideanAlgorithm {
    public static int gcd(int a, int b) {
        // Применяем алгоритм Евклида для нахождения НОД(a, b)
        while (b != 0) {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

public static void main(String[] args) {
        int a = 24;
        int b = 36;
        int gcdValue = gcd(a, b);
        System.out.println("Наибольший общий делитель чисел " + a + " и " + b + " равен " + gcdValue);
    }
}

В данном коде объявлена функция `gcd`, которая принимает два аргумента `a` и `b` - натуральные числа, для которых нужно найти наибольший общий делитель.

Внутри функции используется алгоритм Евклида: пока `b` не равно нулю, выполняется деление `a` на `b` с остатком (переменная `remainder`). Затем значения `b` и `remainder` обмениваются местами, и процесс повторяется до тех пор, пока `b` не станет равным нулю. В конечном итоге, в переменной `a` будет храниться наибольший общий делитель исходных чисел `a` и `b`.

В методе `main` задаются значения `a` и `b`, вызывается функция `gcd` для расчета наибольшего общего делителя и выводится результат на консоль.