C++ Program for Euclid's GCD Algorithm

Euclidean Algorithm is an efficient method of finding the greatest common divisor. It was named after a Greek mathematician Euclid. The Algorithm begins with two positive integers A and B then replaced by X and Y. Then while Y is not zero, at each step X is replaced by Y and then Y is replaced by X mod Y (remainder of a divided by b). The algorithm halts when B = 0.

Pseudo Code for Euclid's GCD Algorithm

Procedure GCD(A, B: positive integers)
X := A
Y := B
while Y != 0
      R := X mod Y
      X := Y
      Y := R
return X {GCD(a,b) is X}

C Plus Plus Program for Euclid's GCD Algorithm

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

void getnum(int &, int &);
void gcd(int, int);

int main ()
{
    int Num1, Num2;
    bool Flag = true;
    string choice;
    while (Flag)
    {
        getnum(Num1,Num2);
        gcd(Num1, Num2);
        cout<<endl <<"Enter N to Exit or Y to get GCD for other numbers: " ;
        cin>>choice;
        if (choice == "N" || choice == "n")
            Flag = false;
    }
    system("pause");
}

void getnum(int &Num1, int &Num2)
{
    cout<<"Enter the First Number: ";
    cin>>Num1;
    cout<<"Enter the Second Number (smaller then First): ";
    cin>>Num2;
    while (Num1 < Num2)
    {
        cout <<"Your Num 1 Must be Greater than Num 2";
        cin>>Num2;
    }
}

void gcd(int Num1, int Num2)
{
    int remainder = Num1 % Num2; // Step 1. Get remainder of two nums
    while (remainder != 0)
    {
        Num1 = Num2; // Step 2. Num 2 becomes Num 1
        Num2 = remainder; // and Remainder becomes Num 2
        remainder = Num1 % Num2;
    }
    cout <<"The GCD is " <<Num2 <<endl;
    return;
}