Introduction

This program will help you to find the GCD of two numbers.

The task is that the user will be asked to enter two integers, and then through this program GCD of both numbers will be computed.

GCD: Greatest common divisor, which is also called as Highest common factor (HCF)

The largest common number that can exactly divide both numbers is GCD. It means there should be no remainder left. Thus, we will use this logic in our code.

There are several methods to compute the GCD. Here we will use the ‘while’ loop.

To understand this example, you should know about some concepts of C++ programming.

1. Operators

2. for loop

3. if, if-else, nested if-else statement

4. while and do-while loop

Note: The program written below will work for both positive numbers or both negative numbers or one positive and one negative number.

Program

#include<iostream>
using namespace std;
int main()
{
int num1, num2;
cout<<"Enter two positive integers: ";
cin>>num1>>num2;
// if the values entered by the user are negative then make them positive


if(num1<0)
{
num1=-num1;
}
if(num2<0)
{
num2=-num2;
}


// computation of GCD
while(num1!=num2)
{
if(num1>num2)
num1=num1-num2;
else
num2=num2-num1;
}
cout<<"GCD: "<<num1;
return 0;
}

Output

Explanation

The values of num1 and num2 can be positive or negative.

First of all, we will convert the negative values to positive values.

if(num1<0)

if num1 is negative, then its sign will get changed using the statement

num1=-num1;

Similarly, for num2.

After that, the while loop is used to compute the GCD.

while(num1!=num2)

The body of the while loop will get executed until both num1 and num2 become equal, and the statements written below will work accordingly.

if(num1>num2)

num1=num1-num2;

else

num2=num2-num1;

The smaller integer is subtracted from, the larger integer, and the result is assigned to the variable holding the larger integer.

Hence the final value of GCD gets stored in num1.