Last Updated on March 23, 2022 by Ria Pathak

### Concepts Used:

Mathematics

### Difficulty Level:

Easy

### Problem Statement (Simplified):

`gcd`

of two given numbers.

`gcd(m,n)`

is the largest number possible which divides both.

**See original problem statement here**

#### Test Case:

```
Input:
1
15 140
Output:
5
Explanation:
5 divides 15 and 140 both and no number larger than 5 divides them completely. So 5 is our answer.
```

### Solving Approach :

*Bruteforce Approach :*

1) We can check all numbers from 1 to the

`Smaller number`

, the largest number which divides both numbers is gcd of both numbers.2) This approach is not efficient as it takes O(

`Smaller Number`

) time complexity, we can use`Long division method`

for efficient approach.

*Efficient Approach :*

We repeatedly store remainder i.e (`Long Division Method`

:`Larger number`

%`Smaller number`

) and update`Larger number`

by`Smaller number`

until`smaller number`

completely divides the`larger number`

. Last`Smaller Number`

after all the steps is our`gcd`

..

#### Example:

Let two numbers are

`25`

and`135`

, so its visual representation for above efficient approach will be,

As soon as our

`reminder`

becomes`0`

, our`dividend`

is our`gcd(a,b)`

.So, 5 is our answer.

### Solutions:

#include <stdio.h> int main() { int test; scanf("%d", &test); while(test--){ int a, b; scanf("%d%d",&a,&b); while(1){ if(b%a==0){ printf("%d\n",a); break; } int temp = a; a = b%a; b = temp; } } }

#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ int a, b; cin>>a>>b; while(true){ if(b%a==0){ cout<<a<<endl; break; } int temp = a; a = b%a; b = temp; } } }

import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); while(test!=0){ int a = sc.nextInt(); int b = sc.nextInt(); while(true){ if(b%a==0){ System.out.println(a); break; } int temp = a; a = b%a; b = temp; } test--; } } }

[forminator_quiz id="1150"]

This article tried to discuss Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Mathematics you can check out MYCODE | Competitive Programming.