The greatest common divisor (GCD) of m and n is defined as the largest number th

Question

The greatest common divisor (GCD) of m and n is defined as the largest number that evenly divides both m and n. The Greek mathematician Euclid devised an elegant solution to the problem that works well as a recursive algorithm.

Base case: m % n = 0 returns n

Otherwise, gcd(m,n) is gcd(n, m % n)

Using the information above, write a recursive Java method named gcd to find the GCD of two numbers m and n. The method is invoked using the main method as shown below.

import java.util.Scanner;
public class FindGCD {
public static void main (String args[]) {
    Scanner input = new Scanner(System.in);
  
    // Enter the first number
    System.out.print("Enter the first number: ");
    int m = input.nextInt();

    // Enter the second number
    System.out.print("Enter the second number: ");
    int n = input.nextInt();

    System.out.println("The GCD of " + m + " and " + n + " is " +
      gcd(m, n));
}

Explanation / Answer

import java.util.Scanner;

public class FindGCD
{
public static void main (String args[])
{
Scanner input = new Scanner(System.in);
  
// Enter the first number
System.out.print("Enter the first number: ");
int m = input.nextInt();

// Enter the second number
System.out.print("Enter the second number: ");
int n = input.nextInt();

System.out.println("The GCD of " + m + " and " + n + " is " +
gcd(m, n));
}
  
public static int gcd(int x,int y)
{
if(y==0) // end of function when y reduces to 0
return x;
else if(y>x)
return gcd(y,x);//if y> x,swap the parameters,recursive call
else
return gcd(y,x%y); //x becomes y and y becomes remainder after dividing x by y
}
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.