This algorithm finds Greatest Common Divisor (GCD) by performing repeated divisi

Question

This algorithm finds Greatest Common Divisor (GCD) by performing repeated division starting from the two numbers we want to find the GCD of until we get a remainder of 0. For example, below are the steps to find the GCD of 60 and 24 using Euclid's algorithm. Divide the larger number by the smaller one. In this case we divide 60 by 24 to get a quotient of 2 and remainder of 12. Next, we divide the smaller number (i.e. 24) by the remainder from the last division (i.e. 12). So we divide 24 by 12. We get a quotient of 2 and remainder of 0. Since we already got a remainder of zero, the last number that we used to divide is the GCD of 24 and 60. In this case 12. Let's look at the steps, find GCD of 24 and 60. 60 ÷ 24 = 2 with a remainder of 12 24 ÷ 12 = 2 with a remainder of 0 We stop here since already got a remainder of 0. The last number we used to divide is 12, so the GCD of 24 and 60 is 12 [2] Description: The program will take two integer numbers as input from the user in an attempt to find the GCD. You should write a program that will take the appropriate input from the user and find out the GCDaccordingly. Youmayassumetheuserinputnumbersarevalid.

Explanation / Answer

Hi, Please find the below program for GCD of two given numbers.

GCDCalculator.java

public class GCDCalculator {
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       java.util.Scanner in = new java.util.Scanner(System.in);
       System.out.println("Please Enter two integer number: ");
       int m = in.nextInt();
       int n = in.nextInt();
       int remainder = 0;
       int count = 0;
       System.out.println("The GCD of two numbers ["+m+"] and ["+n+"] is : " );
       while(true){
           remainder = m % n;
           count++;
           if(remainder != 0){
           m = n;
           n = remainder;
           }
           else{
           System.out.println(n+"["+count+"]");
           break;
           }
          
       }
   }

}

Output1:

Please Enter two integer number:
60
24
The GCD of two numbers [60] and [24] is :
12[2]

Output2:

Please Enter two integer number:
56
17
The GCD of two numbers [56] and [17] is :
1[4]

Steps for Execution:

> Save the above program in file with the file name "GCDCalculator.java"

> Open CMD prompt and go to the path where file has been saved.

> compile the program with below steps

> javac GCDCalculator.java

>java GCDCalculator

> Enter your integer inputs.

> Done

Note: I have not validated the inputs. Assuming like valid inputs will receive from user.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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