Question
One of the oldest numerical algorithms was described by the Greek mathematician, Euclid, in 300 B.C. 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 inte- ger 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 and gcd(x, y) = gcd(x, y − x) 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. This continues until the two values are equal. That is then the gcd.
You are required to do the following:
• Prompt the user to enter two integers and read them from the keyboard.
• Create a loop, and inside of it replace the larger integer with the difference between the larger integer and the smaller integer (if the integers are equal you may choose either one as the “larger”) during each iteration. You will need to use an if/else statement to determine the larger value.
• Continue looping until the two integers are equal.
• Print out the remaining value as the gcd. See the sample output below.
Sample Outputs
Sample 1:
Enter the first integer: 72 Enter the second integer: 54 The gcd of 72 and 54 is 18
Sample 2:
Enter the first integer: 18 Enter the second integer: 24 The gcd of 18 and 24 is 6
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
public static void main(String[] args) {int x, y;
Scanner console = new Scanner(System.in);
System.out.print("Enter the first integer: ");
x = console.nextInt();
System.out.print("Enter the second integer: ");
y = console.nextInt();...