Question

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. The greatest common divisor of a and b is written as gcd (a, b), or sometimes simply as (a, b). For example, gcd (12, 18) = 6, gcd (−4, 14) = 2 and gcd (5, 0) = 5. Two numbers are called co-prime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relative prime. Write a Java code to find/implement gcd (a, b) recursively.

Java Language...

Answer 1

import java.util.*;
class Main
{
   static int gcd(int a, int b) //gcd method
   {
       if (a == 0)
       return b;
       if (b == 0)
       return a;
       if (a == b) //Checking if a=b
           return a;
       if (a > b) //Checking if a>b
           return gcd(a-b, b); //Recursively calling gcd method
       return gcd(a, b-a); //Recursively calling gcd method
   }
  
   public static void main(String[] args)
   {
       int a,b,ans=0; //Declaring variables
       Scanner sc = new Scanner(System.in); //For taking input from user
       System.out.println("Enter the first number: ");
       a = sc.nextInt(); //Taking input from user
       System.out.println("Enter the second number: ");
       b = sc.nextInt(); //Taking input from user
       ans = gcd(a,b); //Calling gcd method and storing result in ans
       System.out.println("GCD of " + a +" and " + b + " is " + ans); //Printing the result
       if(ans==1) //Checking if ans=1
       System.out.println(a+" and "+b+" are relative prime"); //Printing if relative prime
   }
}

Output:-