C Program To Find GCD Of Two Numbers Using Recursion

C Program to find GCD or HCF of two numbers

by

In this tutorial, we are going to learn a writing program in C to calculate GCD or HCF. Basically, Both GCD and HCF are the same. GCD full form is Greatest common divisor and HCF means Highest Common Divisor.

Before starting the writing a program in C for HCF or GCD let’s understand HCF/GCD first.

What is GCD/HCF? How to calculate it?

GCD stands for greatest common divisor (GCD), It is a largest non-zero positive integer of two or more integers that divides each of the integers.

GCD is same as HCF. It can be justify like “greatest common divisor”, the adjective “greatest” may be replaced by “highest”, and the word “divisor” may be replaced by “factor”, so that other name of GCD can be HCF.

How to calculate GCD/HCF?

To calculate GCD of any two or more number, first we will find the factors of the numbers. After that will select the common number and multipy them, resultant will be GCD.

Let’s see an example

Suppose we need to calculate the GCD of 26 and 38.

Factors of 26 = 2 * 13

Factors of 38 = 2 * 19

Here 2 is only the common. So GCD(26,38) will be 2 because only 2 is the highest number that can divide both 26 and 38.

C Program to calculate GCD of two numbers

#include <stdio.h>
int main()
{
    int num1, num2, i, gcd;
    printf("Program to find HCF or GCD of two numbers\n");
    printf("Enter the first number: ");
    scanf("%d", &num1);
    printf("Enter the second number: ");
    scanf("%d", &num2);
    for(i=1; i <= num1 && i <= num2; ++i)
    {
        if(num1%i==0 && num2%i==0)
            gcd = i;
    }
    printf("G.C.D of number %d and %d is %d", num1, num2, gcd);
    return 0;
}

Output

Program to find HCF or GCD of two numbers
Enter the first number: 34
Enter the second number: 12
G.C.D of number 34 and 12 is 2

[wpusb]