14. Write a function that uses Euclid\'s algorithm to calculate the greate commo

Question

14. Write a function that uses Euclid's algorithm to calculate the greate common divisor of its two integer arguments where both arguments are positive and the first argument should be greater than or equal to the second. For example, euclid( 10, 2) is 2, euclid( 20, 12) is _. Euclid's algorithm (int euclid(int m, int n)) forfindingthegreat- est common divisor of m and n follows: [if (m is less than n) // the arguments are in the // wrong order return the result of euclid(n, m) // reverse the // arguments else if (n divides m) // n is a divisor of m return n else return euclid(n, remainder of m divided by n) ] The above algorithm is called a recursive algorithm because function euclid calls itself (a legal operation in C++). If the first condition is true, the arguments need to be reversed before the greatest common divisor can be found by recalling function euclid. If the second con- dition is true, the smaller argument, n, must be the divisor we're seeking. Otherwise, the result can be determined by recalling func- tion euclid to find the greatest common divisor of n and the remain- der of m divided by n. Verify that this algorithm works for the examples shown in the first paragraph. Then write this function and test it out.

Explanation / Answer

#include<iostream>
#include<fstream>
using namespace std;

int euclid(int m,int n){
if(m<n)
return euclid(n,m);// the arguments are in the // wrong order return the result of euclid(n, m)
else if(m%n==0)
return n;// n is a divisor of m return n else
else
return euclid(n, m%n);
}

int main(){
int a,b;//declare variables
int gcd=1;
int test=0;

cout<<"Enter number of tests you want to run: ";
cin>>test;
for(int i=0;i<test;i++){
do{
cout<<"Please enter two positive integers: ";
cin>>a>>b;

}while(a<0||b<0);

gcd=euclid(a,b);
cout<<"The Greatest Common Divisor is: "<<gcd<<endl;

}
cin.get();cin.get();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.