The greatest common divisor of two integers a and b, GCD (a,b), not of which are

Question

The greatest common divisor of two integers a and b, GCD (a,b), not of which are zero, is the largest integer that evenly divides both a and b. The Euclidean algorithm for finding this greatest common divisor is as follows:
1) Divide a by b to obtain the integer quotient q and remainder r so that a=bq+r. Note: if b=0, then GCD(a,b)=a.
2) Now, GCD(a,b) = GCD(b,r) so replace a with b and b with r, and repeat this procedure.

Since the remainders are decreasing, eventually a remainder of 0 will result. The last nonzero remainder is GCD(a,b). For example:
1260=198*6+72________GCD(1260,198)=GCD(198,72)
198=72*2+54__________= GCD(72,54)
72=54*1+18___________= GCD(54,18)
54=18*3+0____________= 18

Write a program that reads two integers and then calls a function named "gcd" that calculates and returns the greatest common divisor. Display the two integers and the greatest common divisor on the terminal screen.

Note: If either a or b is negative, replace it with its absolute value.

Explanation / Answer

public int gcd(int a, int b) { int gcd =0, counter=1; while(counter

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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