C Example for Beginners: C Program to Find GCD of two Numbers

Hits: 30

(C programming Example for Beginners)

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


#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;
}

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


#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: 81
153
GCD = 9

This is a better way to find the GCD. In this method, smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding larger integer. This process is continued until n1 and n2 are equal.

The above two programs works as intended only if the user enters positive integers. Here’s a little modification of the second example to find the GCD for both positive and negative integers.

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: 81
-153
GCD = 9

 

C Example for Beginners: C Program to Find GCD of two Numbers

Sign up to get end-to-end “Learn By Coding” example.



Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.