USING Data Structures Your code must be well formatted and commented. While mark
ID: 671569 • Letter: U
Question
USING Data Structures
Your code must be well formatted and commented. While marks will not be assigned for properly formatting and commenting your code, All programs must include the “Essential Features of Program Documentation” (page 122). Details are included throughout Chapter 2 on best practices for documentation.
Q) Euclid's Algorithm is a well-known algorithm for computing the greatest common divisor (GCD) of two numbers. The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. GCD (a, b) = GCD (b, r) For example, GCD (36, 20) = GCD (20, 16) = GCD (16, 4) = GCD (4, 0) = 4 implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair. Now, Write a method named gcd that computes the greatest common divisor of two.
Explanation / Answer
#include
main()
{
int a, b, temp;
scanf("%d %d", &a, &b);
while(b)
{
temp = b;
b = a%b;
a = temp;
}
printf("%d", a);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.