#include <stdio.h> int gcd_method(int m, int n) { if (n == 0) { return m; } else
ID: 3912037 • Letter: #
Question
#include <stdio.h>
int gcd_method(int m, int n) { if (n == 0) { return m; } else if (m >= n && n > 0) { return gcd_method(n, (m % n)); } }
int main(void) { int num1, num2, gcd; printf(" Enter two numbers to find gcd using Euclid method: "); scanf("%d%d", &num1, &num2); gcd = gcd_method(num1, num2); if (gcd) printf(" GCD of %d and %d is %d ", num1, num2, gcd); else printf(" Invalid/incorrect input "); return 0; } #include <stdio.h>
int gcd_method(int m, int n) { if (n == 0) { return m; } else if (m >= n && n > 0) { return gcd_method(n, (m % n)); } }
int main(void) { int num1, num2, gcd; printf(" Enter two numbers to find gcd using Euclid method: "); scanf("%d%d", &num1, &num2); gcd = gcd_method(num1, num2); if (gcd) printf(" GCD of %d and %d is %d ", num1, num2, gcd); else printf(" Invalid/incorrect input "); return 0; } Write a recursive program in C to find the GCD (greatest common divisor) of two positive numbers m and n by applying the Euclid's method. Euclid's GCD algorithm applies the following rule to calculate GCD of two numbers m and n: if n di idea m with no remainder ? Note: You have to use the Euclid's GCD algorithm (given above) to solve this lab. If you use any other GCD algorithm, you will not get the credit. Examples: GCD of 10 and 15 is 5, GCD of 24 and 30 is 6, GCD of 23 and 24 is 1 etc.
Explanation / Answer
The Euclids algorithm given in the question is almost right, except for a few details. Notice in the gcd_method() function, there seems to be an else if after the if construct. A simple trace by hand method shows the error in loop. By replacing the else if construct with an else takes care of this problem. The new code looks like this:
#include <stdio.h>
int gcd_method(int m, int n)
{
if (n == 0) {
return m;
} else {
return gcd_method(n, (m % n));
}
}
int main(void)
{
int num1, num2, gcd;
printf(" Enter two numbers to find gcd using Euclid method: ");
scanf("%d%d", &num1, &num2);
gcd = gcd_method(num1, num2);
if (gcd)
printf(" GCD of %d and %d is %d ", num1, num2, gcd);
else
printf(" Invalid/incorrect input ");
return 0;
} // There is no change in the main function
To verify take two simple inputs of 2,4
Here, num1=2 num2=4
gcd_method(2, 4)
{
if(4==0) XX // condition fails
else
gcd_method(4, 2) // gcd_method(4,2%4)
{
if(2==0)XX // condition fails
else
gcd_method(2, 0) // gcd_method(2, 4%2)
{
if(0==0) // condition is true
return m // m=2
EXIT FROM RECURSIVE METHOD
In this way, the final output for 2,4 will be 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.