Write a method, public static int gcd(int a, int b) that computes the greatest c

Question

Write a method, public static int gcd(int a, int b) that computes the greatest common divisor of a and b. Do this by implementing Euclid's algorithm: Find q1 and r1, the quotient and remainder of dividing a by b. Then a = b * q1 + r1 Repeat the process, using b and r1 this time, finding a new quotient and remainder: b = r1 * q2 + r2 Again, repeat, moving r1 over, to be the number divided, r2 over to do the dividing and get a new quotient and remainder: r1 = r2 * q3 + r3 The remainders get smaller, because each remainder has to be smaller than the number doing the dividing. So b > r1 > r2 > r3 ... until eventually, say at step n, rn=0. Then the gcd is the last, non-zero remainder. Let's look at an example: gcd(115, 35) 115 = 35 * 3 + 10 35 = 10 * 3 + 5 10 = 5 * 2 + 0 So the gcd(115, 35) is 5. Now you will use this method to simplify fractions. Ask a user to enter the numerator and denominator of a fraction. Make sure the denominator is not 0. Then print the fraction, so it looks like a fraction, in its original and reduced form. In a loop, keep processing until the user indicates that there is no more data (by pressing control-d or control-z). Sample: Enter the numerator: 115 Enter the denominator: 0 Enter the denominator: 35 115 23 --- = --- 35 7 Enter the numerator: 21 Enter the denominator: 222 21 7 --- = --- 222 74 Enter the numerator: control-z

Explanation / Answer

/** * Calculates the greatest common divisor for two numbers. *

* Based on the fact that the gcd from p and q is the same as the gcd from p and * p % q in case p is larger then q * * @author Lars Vogel * */ public class GreatestCommonDivisor { public static int gcd(int p, int q) { if (q == 0) { return p; } return gcd(q, p % q); } // Test enable assert check via -ea as a VM argument public static void main(String[] args) { assert (gcd(4, 16) == 4); assert (gcd(16, 4) == 4); assert (gcd(15, 60) == 15); assert (gcd(15, 65) == 5); assert (gcd(1052, 52) == 4); } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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