Design and implement a program that implements Euclid’s algorithm for finding th
ID: 3695091 • Letter: D
Question
Design and implement a program that implements Euclid’s algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. An iterative version of this method was part of the RationalNumber class presented in Chapter 6. In a class called DivisorCalc, define a static method called gcd that accepts two integers,
num1 and num2. Create a driver to test your implementation. The recursive algorithm is derived as follows:
- gcd(num1, num2) is num2 if num2<=num1 and num2 divides num1
- gcd(num1, num2) is gcd(num2, num1) if num1<num2
- gcd(num1, num2) is gcd(num2, num1%num2) otherwise
Explanation / Answer
this is the program to find gcd of given two positive integers by using the recursive function.
#include<stdio.h>
int main()
{
int num1=0,num2=0,gcd=0;
clrscr();
printf(" Enter two numbers..");
scanf("%d %d",&num1,&num2);
gcd=findgcd(num1,num2);
printf(" GCD of %d and %d is.... %d ",num1,num2,gcd);
getch();
return();
}
//this is the simple recursive function to find the gcd of two numbers....
int findgdc(int x, int y)
{
while(x!=y)
{
if(x>y)
return findgcd(x-y,y);
else
return findgcd(x,y-x);
return x;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.