Program Find GCD or HCF of Two Whole Numbers

Before writing the program GCD in C Plus Plus, let us understand the logic of the GCD program. 

Program to Find GCD of two integer numbers in See Plus Plus C++

What is GCD?

GCD stands for  Greatest Common Divisor. GCD of two or more integer numbers is the largest positive integer that divides the given numbers without a remainder. For example,

• GCD of 8 and 12 is 4
• GCD of 24 and 36 is 12
• GCD of 7 and 1 is 1
• GCD of 50 and 35 is 5

Note: GCD is also known as GCF - Greatest Common Factor or HCF - Highest Common Factor or HGD - Highest Common Divisor.

One Method of Calculating GCD

Question: What is the GCD of (24, 56). 
Factors of 24 are 2 * 2 * 2 * 3,
Factors of 56 are 2 * 2 * 2 * 7.
The Common factors are 2 * 2 * 2 = 8.
Therefore the GCD of (24, 56) is 8.

Question: What is the GCD of (18, 27). 
Factors of 18 are 2 * 3 * 3
Factors of 27 are 3 * 3 * 3
The Common factors are 3 * 3  = 9
Therefore the GCD of (18, 27) is 9

 

Program Logic: GCD of Two Numbers a and b.

• We will divide the greater number by the smaller number. If it is divided with no remainder then smaller number is GCD. For Example let a = 18 and b = 6. We will divide 18 by 6. It is divided with no remainder. So GCD is 6.
•  Let a  = 18 and b = 27. Now we divide 27 by 18. It is not divided evenly. So we will divide 27 by 17, 16, 15, 14 and so on to 1. When we will divide 27 by 9, it will be divided evenly. So 9 is the GCD.

 Write a C++ Program to input two integer numbers
and Find the GCD.

 /*
Write a C++ Program to input two integer numbers
and Find the GCD.

For Free C++ Programming Techniques (Example Programs), visit
Www.EasyCppProgramming.Blogspot.Com

and For Good Notes
Visit   Www.ForFreeEducation.Blogspot.Com
*/
#include<iostream.h>

#include<conio.h>

void main()
{

  clrscr();

  int a, b, counter;

  cout<<"\n Enter the first number = ";

  cin>>a;

  cout<<"\n Enter the second number = ";

  cin>>b;

  if ( a < b )
     counter = a;
     else
     counter = b;

  for(; counter>=1; counter -- )

    if ( a % counter == 0 && b % counter == 0 )
         break;

  cout<<"\n\n -------- Results --------\n";

  cout<<"\n GCD of "<<a<<" and "<<b<<" is = "<<counter;
 
  getch();

}