Originally Posted by
pwr_hngry Hello again,
Here is another one that is giving me trouble.
I have 2 given integers: 110, 273
I am supposed to find the greatest common divisor of the pair using the Euclidean Algorithm:
Input: a and b (nonnegative integers, not both zero)
Output: Greatest common divisor of a and b
gdc(a,b) {
if(a<b)
swap(a,b)
while (b not=0) {
r=a mod b
a = b
b = r
}
return a
}
hope this makes sense.
Any help with this would be greatly appreciated.
Pwr
Note there is no need to do the swap, as if a<b first time through the
while loop will swap them as:
a mod b = a
if a<b.
So you can neaten your algorithm to:
Code:
gdc(a,b) {
while (b not=0) {
r=a mod b
a = b
b = r
}
return a
}
RonL