Question

Java program:

Greatest Common Divisor

Write a program which finds the greatest common divisor of two natural numbers a and b

Input:  a and b are given in a line separated by a single space.

Output: Output the greatest common divisor of a and b.

Constraints: 1 ≤ a, b ≤ 10⁹

Hint: You can use the following observation:

For integers x and y, if x ≥ y, then gcd(x, y) = gcd(y, x%y)

Sample Input 1

54 20

Sample Output 1

2

Sample Input 2

147 105

Sample Output 2

21

Answer 1

Below is the code for the question above in JAVA :

import java.util.Scanner;

public class Main{
static int g;
  
static int gcd(int a, int b)
{
  
for(int j = 1; j <= a && j <= b; j++)
{
if(a%j==0 && b%j==0)
  
g = j;
  
}
  
return g;
}

   public static void main(String[] args)
   {
       Scanner obj1 = new Scanner(System.in);
  
   System.out.println("Enter the value of a and b");
  
   int g=1;
   int a = obj1.nextInt();
   int b = obj1.nextInt();
  
   System.out.printf("%d %d", a,b);
  
   System.out.println(" ");
  
  

System.out.printf("%d", gcd(a,b));
  
   }
}

Screenshot for the output: