Practice-It! logo

BJP3 Exercise 5.2: gcd

Added by: Leslie Ferguson on 2013/04/01
Language: Java
Keywords: while, %, return

Write a method named gcd that accepts two integers as parameters and returns the greatest common divisor of the two numbers. The greatest common divisor (GCD) of two integers a and b is the largest integer that is a factor of both a and b. The GCD of any number and 1 is 1, and the GCD of any number and 0 is that number.

One efficient way to compute the GCD of two numbers is to use Euclid's algorithm, which states the following:

GCD(A, B) = GCD(B, A % B)
GCD(A, 0) = Absolute value of A

In other words, if you repeatedly mod A by B and then swap the two values, eventually B will store 0 and A will store the greatest common divisor.

For example: gcd(24, 84) returns 12, gcd(105, 45) returns 15, and gcd(0, 8) returns 8.

Method problem: For this problem, you are supposed to write a Java method as described. You should not write a complete Java class; just write the method(s) described in the problem statement.

You must log in before you can solve this problem.

Log In

indent Re-indent

If you do not understand how to solve a problem or why your solution code doesn't work, please contact your TA or instructor.

If something seems wrong with the Practice-It system itself (errors, slow performance, incorrect problem descriptions/tests, etc.), please contact us.

Is there a problem?
Contact a Practice-It administrator.