Write a compete program that implements the following algorithm that computes th

Question

Write a compete program that implements the following algorithm that computes the greatest common divisor of two given positive integers. For example, if 441 and 252 are input, then the program should print that 36 is their greatest common divisor:

Euclid’s algorithm: Given two positive integers m and n, find their greatest common divisor, i.e., the largest positive integer which evenly divides both m and n.
1. [Find remainder] Divide m by n and let r be the remainder. (We will have 0 ? r ? n.)
2. [Is it zero?] if r = 0, the algorithm terminates; n is the answer.
3. [Interchange.] Set m ? n, n ? r, and go back to step 1.

Explanation / Answer

please rate - thanks

your example should read 63 not 36

#include <iostream>
using namespace std;
int main()
{int m,n,r;
cout<<"enter a number: ";
cin>>m;
cout<<"enter another number: ";
cin>>n;
cout<<"The greatest common divisor of "<<m<<" and "<<n<<" is ";
r=m%n;
while(r!=0)
{m=n;
n=r;
r=m%n;
}
cout<<n<<endl;

system("pause");
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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