## 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^{1} 41^{1}

152 = 2^{3} 19^{1}

The answer is: 2^{1} = 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