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

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

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


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 можно вычисляться нерекурсивно, например, с помощью следующего кода.

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++