Finding Greatest Common Divisors One of the oldest numerical algorithms was desc

Question

Finding Greatest Common Divisors One of the oldest numerical algorithms was described by the Greek mathematician, Euclid, in 300 B.C. That algorithm is described in Book VII of Euclid's multi-volume work Elements. It is a simple but very effective algorithm that computes the greatest common divisor of two given integers. For instance, given integers 24 and 18, the greatest common divisor is 6, because 6 is the largest integer that divides evenly into both 24 and 18. We will denote the greatest common divisor of x and y as gcd(x, y). The algorithm is based on the clever idea that the gcd(x, y) = gcd(x - y, y) if x >= y. The algorithm consists of a series of steps (loop iterations) where the "larger" integer is replaced by the difference of the larger and smaller integer. In the example below, we compute gcd(72, 54) and list each loop iteration computation on a separate line. The whole process stops when one of the integers becomes zero. When this happens, the greatest common divisor is the non-zero integer. To summarize: Create a loop, and subtract the smaller integer from the larger one (if the integers are equal you may choose either one as the "larger") during each iteration. Replace the larger integer with the computed difference. Continue looping until one of the integers becomes zero. Print out the non-zero integer. Use the code below to prompt the user for the two integers.

Explanation / Answer

import java.util.Scanner;

public class GCD {

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.println("Enter the first integer: ");
       int x = sc.nextInt();
       System.out.println("x= "+x);
       System.out.println("Enter the second integer: ");
       int y = sc.nextInt();
       System.out.println("y= "+y);
      
       //gcd code;
       int max = x;
       int min = y;
       int gcd = 0;
       while(true){
          
           // if one of them is zero, non-zero element will be gcd
           if(x == 0){
               gcd = y;
               break;
           }
           if(y ==0 ){
               gcd = x;
               break;
           }
          
           // other wise repeat steps
           max = ((x > y) ? x :y);// getting max of two
           min = ((x > y) ? y : x); // getting minimum of two
           //System.out.println("max= "+max+" min= "+min);
           x = max - min;
           y = min;
       }
       System.out.println("GCD: "+gcd);
   }
}

/*

Output:

Enter the first integer:
12
x= 12
Enter the second integer:
15
y= 15
GCD: 3

*/

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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