## Main Page → Problems → Solve a Problem

## BJP3 Exercise 5.2: gcd

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.

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.