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 only for positive numbers.

Program

#include<iostream>
using namespace std;
int main()
{
int num1, num2;
cout<<"Enter two positive integers: ";
cin>>num1>>num2;


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

Output

Explanation

num1and num2 contain two positive values 16 and 76 respectively.

The while loop is used to compute the GCD.

while(num1!=num2)

The body of the while loop will get execute 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.