GCD of two numbers

Last Updated on March 23, 2022 by Ria Pathak

Concepts Used:

Mathematics

Difficulty Level:

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

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.