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

//GCD.java
/**The java program that prompts user to enter two integer values.
* Then finds the gcd (greatest common factor) of two integer
* and prints to console*/
import java.util.Scanner;
public class GCD
{
   public static void main(String[] args)
   {
       Scanner in=new Scanner(System.in);
      
       System.out.println("Enter first integer");
       int x=in.nextInt();
      
       System.out.println("x = "+x);
      
       System.out.println("Enter first integer");
       int y=in.nextInt();
      
       //print y value
       System.out.println("y = "+y);
      
      
       //Call gcd method on x and y      
       //print gcd value
       System.out.println("GCD of "+x+" and "+y+" is "+gcd(x,y));
      
   }

   /*The method gcd that takes two integer X and Y as arguments
   * and returns gcd of two values*/
   private static int gcd(int X, int Y)
   {
       // Assign to x and y values
       int x=X;
       int y=Y;
      
       //Repeat loop and conditnue until both are not equal
       //In loop check if x is greter than y
       //Then subtract y from x and assign to x
       //else subtract x from y and assign to y
       while(x!=y)
       {
           if(x>y)
               x=x-y;          
           else
               y=y-x;
       }
              
       //Since both are equal then return any value x or y
       //return x vlaue
       return y;
   }
}

-----------------------------------   -----------------------------------   ----------------------------------- -----------------------------------

Sample Output:

Enter first integer
72
x = 72
Enter first integer
54
y = 54
GCD of 72 and 54 is 18

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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