Challenge: Euclidean Algorithm

Euclidean algorithm

The Euclidean algorithm is a technique used to compute the greatest common divisor (GCD) of two numbers, i.e., the largest number that divides both of them without leaving a remainder.

The Euclidean algorithm is based on the principle that the greatest common divisor (GCD) of two numbers does not change if the larger value of the two is replaced by the difference between both numbers. Or, one can get to the result faster if the remainder operator is used instead of simply using the difference. Keep this logic in mind while solving the following challenge.

Problem statement

Given two integers a and b, calculate the largest number (GCD) that divides both of them without leaving a remainder.

Input

The inputs are two integers x and y

Output

The output is x & y’s GCD.

Sample input

x = 15 , y = 75

Sample output

GCD = 15