answersLogoWhite

0


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.
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.

User Avatar

Wiki User

โˆ™ 2012-08-20 20:54:44
This answer is:
User Avatar
Study guides

What is a programming language

What does DOS stand for

What is a software that is distributed for free

What is application software

โžก๏ธ
See all cards
3.79
โ˜†โ˜…โ˜†โ˜…โ˜†โ˜…โ˜†โ˜…โ˜†โ˜…
19 Reviews

Add your answer:

Earn +20 pts
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?
magnify glass
imp
Related questions

What is the greatest common denominator of 14 and 49?

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


What is the greatest common denominator of 6 and 8 and 9?

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


What is the greatest common denominator of 12 18 and 21?

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


What is the greatest common denominator of 4 6 10 and 22?

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


What is the greatest common denominator of 91 156 and 169?

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


How do you know if fractions are integers?

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


What is the name of a ratio where the numerator and denominator are both integers?

And the denominator is 0


What is the symbol for integers were does it come from and what does it mean?

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.


Why java integer takes 4 bytes?

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


A ration of 2 integers where the denominator 0?

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


Are improper fractions integers?

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


What is a ratio of 2 integers where the denominator equals 0?

A ratio with denominator 0 is not defined.

People also asked