   0

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

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.
18A divided by 12B gives a quotient of 1C and a remainder of 6D.

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

The Euclidean algorithm works like this:

1. 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.
2. Check if either of the two integers is 1. If so, 1 is the GCD.
3. Divide the larger of the two integers by the smaller.
4. Divide the divisor of the previous division operation by the remainder of the previous operation.
5. 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.

1. Check to see if either 84 or 18 is equal to 0. Nope. Continue on...
2. Check to see if either 84 or 18 is equal to 1. Nope. Continue on...
3. Since 84 is larger than 18, divide 84 by 18. Quotient is 4, remainder is 12.
4. 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.
5. 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.
6. 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

20 cards

## What is application software

➡️
See all cards
3.79
19 Reviews Earn +20 pts  