Question

Consider the following C program
main( )
{
int x, y, m, n;
scanf ('%d %d", &x, &y);
/* Assume x > 0 and y > 0*/
m = x; n = y;
while(m! = n)
{
if (m > n)
m = m-n;
else
n = n - m;
}
printf("% d", n);
}
The program computes

• A. x mod y using repeated subtraction
• B. the greatest common divisor of x and y
• C. the least common multiple of x and y
• D. x$÷$y, using repeated subtraction

Answer 1

The correct option is B the greatest common divisor of x and y

The given C program is non-recursive. So we will get the value of n after some iteration. The main thing about the program is that.

1. if m = n then n is the GCD
2. if m > n then m = m- n
3. if m < n then n = n- m

For example let x= 40 and y = 32
m = x = 40 and n = y = 32
m > n so apply the 2nd condition
m = m - n
m = 40 - 32 = 8
m = 8 and n = 8
apply the first condition
GCD (40, 32) = 8