Алгоритм Евклида нахождения НОД двух чисел (реализация на Java)

Java   2 Февраль 2012  Автор статьи:  

Приведем реализацию алгоритма Евклида нахождения наибольшего общего делителя двух целых неотрицательных чисел. В качестве аргументов методу gcd передаются 2 числа, в качестве результата он возвращает их НОД. Вычисления производятся с типом данных int (при необходимости, разумеется, можно заменить его на любой другой целочисленный).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.PrintWriter;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        // Для считывания воспользуемся классом Scanner
        // Для вывода - классом PrintWriter
        Scanner scanner = new Scanner(System.in);
        PrintWriter printWriter = new PrintWriter(System.out);

        int a;
        a = scanner.nextInt();
        int b;
        b = scanner.nextInt();

        printWriter.println(gcd(a, b));

        // После выполнения программы необходимо закрыть
        // потоки ввода и вывода
        scanner.close();
        printWriter.close();
    }

    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

Очевидно, метод gcd можно вычисляться нерекурсивно, например, с помощью следующего кода.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int gcd(int a, int b) {
    while (a != 0 && b != 0) {
        if (a > b) {
            a %= b;
        } else {
            b %= a;
        }
    }

    // Так как после выполнения цикла одна из
    // переменных гарантированно равна нулю, то
    // сумма (a + b) будет НОД
    return a + b;
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++