C Program to Find GCD of two Numbers

C Program to Find GCD of two Numbers

Examples on different ways to calculate greatest common divisor (gcd) of two integers (vlaue of both positive and negative integers ) using loops and decision making statements in C programing.

The HCF (highest common factor) or GCD (greatest common divisor) of two integers is the largest integer that can exactly divide both numbers (without a remainder).

hear we will show you 3 different way to find greatest common divisor (gcd).

Simple calculate and method of GCD

82 = 2¹ 41¹ 
152 = 2³ 19¹ 

The answer is: 2¹  = 2

Example 1 :: GCD Using for loop and if Statement

// include header file
#include <stdio.h>

// main function
int main()
{
    int num1, num2, i, gcd;
	
	// insert data  
    printf("Enter two integers value : ");
    scanf("%d %d", &num1, &num2);

	// calculate gcd
    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;
    }
	// print result
    printf("\nGCD of %d and %d = %d", num1, num2, gcd);
	// return 0
    return 0;
}

Output

Enter two integers value :  82 
152
GCD of 82 and 152 = 2

In this program, two integers entered by the user are stored in variable num1 and num2. loop is iterated until “i” is less than “num1” and “num2”.

In each iteration, if both “num1” and “num2” are exactly divisible by “i”, the value of “i” is assigned to gcd.

When the for loop is completed, the greatest common divisor(gcd) of two numbers is assigned in variable “gcd”.

Example 2 :: GCD Using while loop and if-else Statement

// include header file
#include <stdio.h>

// main function
int main()
{
    int num1, num2;
    
	// insert data  
    printf("Enter two positive integers value : ");
    scanf("%d %d",&num1,&num2);
	
	// calculate gcd
    while(num1!=num2)
    {
        if(num1 > num2)
            num1 -= num2;
        else
            num2 -= num1;
    }
	
	// print result
    printf("\nGCD IS = %d",num1);
	// return 0
    return 0;
}

Output

Enter two positive integers value : 82 
152
GCD IS = 2

This is a better way to find the greatest common divisor(GCD). In this method, smaller integer is subtracted from the larger integer, and the result is assigned to variable who is holding larger integer value. This process is continued until “num1” and “num2” are equal.

The above two programs works as intended only if the user pass positive integers(value). Here is a little change of the second example to find the GCD for both positive and negative type of integers.

Example 3 :: GCD for both positive and negative numbers

// include header file
#include <stdio.h>

// main function
int main()
{
    int num1, num2;
	
	// insert data  
    printf("Enter two integers value : ");
    scanf("%d %d",&num1,&num2);

    // if user enters negative number, 
	// then sign of the number will be changed to positive
    num1 = ( num1 > 0) ? num1 : -num1;
    num2 = ( num2 > 0) ? num2 : -num2;

	// calculate gcd
    while(num1!=num2)
    {
        if(num1 > num2)
            num1 -= num2;
        else
            num2 -= num1;
    }
	
	// print result
    printf("\nGCD IS = %d",num1);
	// return 0
    return 0;
}

Output

Enter two integers value : 82 
-152
GCD IS = 2