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 ‘for’ 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;
// we will find a value that divides num1 and num2 completely
int GCD;
for(int i=1; i<=num1 && i<=num2; i++) // 'i' must be less than both of the numbers
{
if (num1%i==0 && num2%i==0) // if 'i' is completely dividing both the numbers
{
GCD=i;
}
}
cout<<"GCD of "<<num1<<" and "<<num2<<" is "<<GCD;
return 0;
}

Output

Explanation

num1 and num2 contains two positive values, 25 and 625, respectively.

int GCD; declaration of the ‘GCD’ variable

for(int i=1; i<=num1 && i<=num2; i++)

the above loop will iterate until ‘i’ remains less than equal to both num1 and num2

if (num1%i==0 && num2%i==0)

This condition will get checked in each iteration, if both num1 and num2 are exactly divisible by i, the value of i will be assigned to GCD.

Since at i=25 the above condition becomes true thus, the value of GCD printed is 25.