Best Answer

The easiest way to find the greatest common denominator of two integers with a computer program is to use the Euclidean algorithm. Of the most popular methods of finding the GCD of two numbers, the Euclidean algorithm does it with the least amount of work and requires the least amount of code.

In order to understand the Euclidean algorithm, you'll need to know a few division terms:

- The dividend is the number to be divided.
- The divisor is the number being divided by.
- The quotient is the number of times the divisor divides into the dividend.
- The remainder is the amount "left over" when the divisor cannot go into the dividend an integral number of times.

A is the dividend, B is the divisor, C is the quotient, and D is the remainder.

The Euclidean algorithm works like this:

- Check if either of the two integers is 0. If so, there is no solution (Ø), as a number cannot share a GCD with zero. Besides, division by zero is a big no-no.
- Check if either of the two integers is 1. If so, 1 is the GCD.
- Divide the larger of the two integers by the smaller.
- Divide the divisor of the previous division operation by the remainder of the previous operation.
- Repeat step four until the remainder equals zero. When the remainder equals zero, the divisor of the last operation is the GCD.

If you still don't get it, try looking at the Euclidean algorithm in action:

Find the GCD of 84 and 18.

- Check to see if either 84 or 18 is equal to 0. Nope. Continue on...
- Check to see if either 84 or 18 is equal to 1. Nope. Continue on...
- Since 84 is larger than 18, divide 84 by 18. Quotient is 4, remainder is 12.
- Take the divisor of the last operation (18) and divide it by the remainder of the last operation (12). Quotient is 1, remainder is 6.
- Take the divisor of the last operation (12) and divide it by the remainder of the last operation (6). Quotient is 2, remainder is 0.
- When the remainder is 0, the divisor of the last operation is the GCD. So the GCD in this case is 6.

You should now have a good grasp of how the Euclidean algorithm works. Now we need to turn it into code. We'll need three variables, all of them integers:

int divisor, dividend, remainder;

The purpose of the variables is self-explanatory. Next, we need to make a few decisions. We need to decide if the dividend or the divisor is 0. If that test is passed, then we need to decide if the dividend or the divisor is 1. If that test is passed, then we need make sure that dividend is larger than divisor.

if(dividend 1) {

printf("The GCD is 1.\n");

}

// Make sure the dividend is greater than the divisor.

if(divisor > dividend) {

remainder = dividend;

dividend = divisor;

divisor = remainder;

}

// Calculate the GCD.

while(remainder != 0) {

remainder = dividend % divisor;

dividend = divisor;

divisor = remainder;

}

// Display the answer to the user.

printf("The GCD is %i.\n", dividend);

}

And the GCD lived happily ever after. The end.

Study guides

☆☆

Q: Using the C or similar programming languages how can I find the greatest common denominator of two integers?

Write your answer...

Submit

Still have questions?

Related questions

The greatest common denominator of any set of integers is infinite.

The greatest common denominator of any set of integers is infinite.

The greatest common denominator of any set of integers is infinite.

The greatest common denominator of any set of integers is infinite.

The greatest common denominator of any set of integers is infinite.The greatest common factor of this group is 13.

Fractions are integers when their denominator is 1 or when the numerator has the same value as the denominator.

And the denominator is 0

The symbols for integers (not the set of integers) are often the letters n, i, j and k. In some early programming languages, any variable whose name started with the letters i to n (inclusive) was an integer variable.

32-bit integers are common in programming languages, and the Java developers simply decided to stick with convention.

A ration with 2 integers and has a denominator of 0 would be called rational numbers. This is taught in algebra.

No, they are improper fractions. They can be equivalent to integers if the numerator is a multiple of the denominator.

A ratio with denominator 0 is not defined.

People also asked