1.2k views

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$

It is an algorithm for $\gcd$ computation.

Here, while loop executes until $m=n$.
We can test by taking any two numbers as $m,n$.

edited
+1
c) euclidean algorithm