GCD or HCF of two numbers

Posted on Apr 8, 2020

C Program to Find GCD/HCF of two Numbers.

The HCF (Highest Common Factor) or GCD (Greatest Common Divisor) of two integers is the largest integer that can exactly divide a given number without leaving a remainder.

The GCD of two numbers 8 and 12 is 4 because, both 8 and 12 are divisible by 1, 2, and 4 (the remainder is 0) and the largest positive integer among the factors 1, 2, and 4 is 4.

Mathematically, GCD can be calculated as follows:

Program 

#include<stdio.h>
#include<conio.h>
void main()
{
	int num1, num2, i, gcd;

    printf("Enter two integers: ");
    scanf("%d%d",&num1,&num2);

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

    for(i=1; i <= num1 && i <= num2; i++)
    {
        // Checks if i is factor of both integers
        if(num1%i==0 && num2%i==0)
            gcd = i;
    }

    printf("G.C.D of %d and %d is %d", num1, num2, gcd);

    getch();
}
C++

Output 

Enter two integers: 9
24
G.C.D of 9 and 24 is 3
Bash