C Program to Find GCD of two Numbers

* Examples on different ways to calculate GCD of two integers (for both positive and negative integers) using loops and decision making statements.

* The HCF or GCD of two integers is the largest integer that can exactly divide both numbers (without a remainder).

* There are many ways to find the greatest common divisor in C programming.

Example #1: GCD Using for loop and if Statement :

Program :

#include <stdio.h>
int main()
{
    int n1, n2, i, gcd;

    printf("Enter two integers: ");
    scanf("%d %d", &n1, &n2);

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

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

    return 0;
}

Output :

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

* In this program, two integers entered by the user are stored in variable n1 and n2.Then, for loop is iterated until i is less than n1 and n2.

* In each iteration, if both n1 and n2 are exactly divisible by i, the value of i is assigned to gcd.

* When the for loop is completed, the greatest common divisor of two numbers is stored in variable gcd.

Example #2: GCD Using while loop and if...else Statement :

Program :

#include <stdio.h>
int main()
{
    int n1, n2;
    
    printf("Enter two positive integers: ");
    scanf("%d %d",&n1,&n2);

    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("GCD = %d",n1);

    return 0;
}

Output :

Enter two positive integers: 54
98
GCD = 2

Example #3: GCD for both positive and negative numbers :

#include <stdio.h>
int main()
{
    int n1, n2;

    printf("Enter two integers: ");
    scanf("%d %d",&n1,&n2);

    // if user enters negative number, sign of the number is changed to positive
    n1 = ( n1 > 0) ? n1 : -n1;
    n2 = ( n2 > 0) ? n2 : -n2;

    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("GCD = %d",n1);

    return 0;
}â€‹

Output :

Enter two integers: 32
-71
GCD = 1â€‹