Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# GCD of two numbers

Last Updated on March 23, 2022 by Ria Pathak

Mathematics

Easy

### Problem Statement (Simplified):

Print `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 :

`Long Division Method`: We repeatedly store remainder i.e (`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)`.

### 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.