66 Introduction to C++ Programming and Graphics
Euclid’s algorithm produces the GCD by repeatedly subtracting the
smaller from the larger integer, and then abandoning the larger integer in favor
of the difference. If at any stage the two integers are the same, the GCD has
been identified.
The method is implemented in the following code contained in the file
euclid.cc:
#include <iostream>
using namespace std;int main()
{
int n=100, m=100, k, save;cout<<"\n Will compute the Greatest Common Divisor";
cout<<"\n\t of two positive integers\n";
again:
cout<<"\n Please enter the first integer";
cout<<"\n\t 0 quit"<< endl;
cin>>n;if(n==0) goto quit;cout<<" Please enter the second integer";
cout<<"\n\t 0 quit\n";
cin>>m;if(m==0) goto quit;if(n==m)
{
k=n;
cout<<"\nThe Greatest Common Divisor is: "<<k<<endl;
}
else while (n!=m)
{
if(n>m) // switch n and m to ensure n<m
{
save=m;
m=n;
n=save;
}
k=m-n; // replace (n,m) with (k,n)
m=n;
n=k;
if(n==m) // done
{
k=n;