# Greatest Common Divisor

Posted: 9 Dec, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### The Greatest Common Divisor of any two integers is the largest number that divides both integers.

##### For Example:
``````You are given ‘X’ as 20 and ‘Y’ as 15. The greatest common divisor, which divides both 15 and 20, is 5. Hence the answer is 5.
``````
##### Input Format:
``````The first line of input contains ‘T’, representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘X’ and ‘Y’, representing the given numbers.
``````
##### Output Format:
``````For each test case, print a single integer representing the Greatest Common Divisor of ‘X’ and ‘Y’.

Print a separate line for each test case.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= X, Y <= 10^9
`````` Approach 1

In this approach, we know the minimum value of a common factor of two integers is 1, and the maximum value of a common factor is the minimum value of the given two integers.

Therefore we will maintain a variable ans to store GCD. We set the initial value of ans as 1. We will iterate through the integers from 2 to the minimum of X and Y. We will check for each integer if X and Y are divisible by the integer, then update the ans with the integer. In the end, we return the variable ans.

Algorithm:

• Set the variable ans as 1. The variable ans stores the greatest common divisor of X and Y.
• Iterate num from 2 to the minimum of X and Y.
• If X and Y are divisible by num, set ans as num.
• Finally, return the variable ans.