Алгоритъм на Евклид

Алгоритъмът на Евклид е алгоритъм за намиране на най-големия общ делител (НОД) на две естествени числа. Взимайки двете дадени на входа на алгоритъма числа a и b, провери дали b е равно на 0. Ако да, числото a е търсеният най-голям общ делител. Ако не, повтори процеса, като използваш за входни данни b и остатъка, получен при деленето a на b (означаван по-долу с a mod b)

Цитат от Wikipedia

Реализация в Java

Решаваме задачата с използване на рекурсия. За упражнение на читателя оставям реализирането на вариант с оператор за цикъл.

public class Euclid {
 
    public static void main(String args[]) {
        System.out.print("Въведете първо число: ");
        java.util.Scanner in = new java.util.Scanner(System.in);
        int x = in.nextInt();
        System.out.print("Въведете второ число: ");
        int y = in.nextInt();
        System.out.println("НОД на двете числа: " + gcd(x, y));
    }
 
    static int gcd(int x, int y){
        if(y == 0) return x;
        else return gcd(y, x % y);
 
    }
 
}