Design and implement a program that implements Euclid’s algorithm for finding th

Question

Design and implement a program that implements Euclid’s algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. An iterative version of this method was part of the RationalNumber class presented in Chapter 6. In a class called DivisorCalc, define a static method called gcd that accepts two integers,

num1 and num2. Create a driver to test your implementation. The recursive algorithm is derived as follows:

- gcd(num1, num2) is num2 if num2<=num1 and num2 divides num1

- gcd(num1, num2) is gcd(num2, num1) if num1<num2

- gcd(num1, num2) is gcd(num2, num1%num2) otherwise

Explanation / Answer

DivisorCalc.java

import java.util.Scanner;

public class DivisorCalc {

   public static void main(String[] args) {
       // Declaring variables
       int num1, num2;

       // Scanner object is used to get the inputs entered by the user
       Scanner sc = new Scanner(System.in);

       // Getting the inputs entered by the user
       System.out.print("Enter the Number#1 :");
       num1 = sc.nextInt();

       System.out.print("Enter the Number#2 :");
       num2 = sc.nextInt();

       // calling the method by passing the user entered inputs as arguments
       int greatestComDiv = gcd(num1, num2);

       // Displaying the gcd of two numbers
       System.out.println("The GCD of " + num1 + " and " + num2 + " is :"
               + greatestComDiv);

   }

   // This static method calculate the gcd of two numbers using recursion
   private static int gcd(int num1, int num2) {
       if (num2 == 0) {
           return num1;
       }
       return gcd(num2, num1 % num2);

   }

}

__________________

Output:

Enter the Number#1 :45
Enter the Number#2 :12
The GCD of 45 and 12 is :3

______________Thank You

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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