Given two integers, x and y, a recursive technique to find their GCD is the Euclidean Algorithm.

The algorithm states that, for computing the GCD of two positive integers x and y, if x and y are equal, GCD(x, y) = x. Otherwise GCD(x, y) = GCD(x - y, y) if x > y. There are a few optimizations that can be made to the above logic to arrive at a more efficient implementation.

**Task**

Given the starter code, you need to complete a function body that returns the GCD of two given integers x and y.

The task of reading in input and printing the output will be handled by us.

**Input Format**

One line of input containing space separated integers.

**Output Format**

Output one integer, the GCD of the two given numbers.

**Sample Input**

1 5

**Sample Output**

1

**Constraints**

Sample Return Values:

GCD(1,5) = 1

GCD(10,100) = 10

GCD(22,131) = 1

**Solution**

import java.io.*;

import java.util.*;public class Solution {

public static void main(String[] args) {

Scanner reader = new Scanner(System.in);

int first = reader.nextInt();

int second = reader.nextInt();

System.out.println(gcd(first, second));

}

public static int gcd(int m, int n){

if(n == 0)

return m;

else

return gcd(n, m%n);

}

}

**The code listed above may or may not be the "best" solution. Please be advised that this is just the way I did it. There are normally thousands of different ways to solve the same programming problem. Find an error? Let me know in the contact form below.**

Feel free to email me feedback, suggestions, notes, or to just say hello!