Consider the following C program : main ()

Home » Programming & Data Structure » Programming and data structure miscellaneous » 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

1. x + y using repeated subtraction
2. x mod y using repeated subtraction
3. the greatest common divisor of x and y
4. the least common multiple of x and y

Correct Option: C

This is an implementation of Euclid's algorithm to find GCD
Here if m > n, then m = m – n
m < n, then n = n – m
Let take X = 24, Y = 9
Then m = 24, n = 9

iteration	m	n
1	24 – 9 = 15	9
2	15 – 9 = 6	9
3	6	9 – 6 = 3
4	6 – 3 = 3	3

Here m = n, so n returned
Which is GCD (Greatest common divisor) of X&Y
Hence (c) is correct option.