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.