GCD of Two Numbers in C

• The GCD means the greatest common divisor of two or more integers, it is also called as hcf. The gcd returns the greatest integer of the given two integers that divides the numbers without leaving any remainder.
• For example, for the two numbers 5 and 10, both 5 and 10 are divisible by 1 and 5. Since 5 is greater than 1, the gcd of 5 and 10 is 5.
• We can find the gcd of two numbers using loops and statements.
  Program 1: GCD of two numbers using if statement and for loop

/ / program to find out gcd of two numbers
#include <stdio.h>
/ / main function
Int main () 
{
/ / declaring the variable
Int a, b, i, gcd;
Printf(“ Enter the two numbers : “);
Scanf(“%d %d “,&a,&b);
for(Ii= 1; i <= a && i <= b;i++)
{
/ / checks whether i is a factor for two integers
If( a% i == 0 && b % i == 0)
{
gcd = i;
} }
Printf(“ The gcd of two numbers is %d” , gcd);
return 0;
}

Output:

Enter two numbers: 8

12

The gcd of two numbers is 4

• In the above program, the for loop is used to block the i value to not to check beyond the user-specified values
  
  The gcd of two numbers using while loop:

/ / gcd of two numbers using while loop
#include <stdio.h>
/ / main function
Int main () {
/ / declaring the variable
Int a, b, gcd, temp;
Printf(“ Enter the two numbers : “);
Scanf(“%d %d “,&a,&b);
/ / using while loop
while (b != 0) {
temp = b;
b = a % b;
a = temp:
}
Gcd = a;
Printf(“ The gcd of two numbers is %d ”, gcd);
return 0;
}

Output: Enter the two numbers: 8 12

The gcd of two numbers is 4

• In the above program, in the while loop, we are checking whether the b is equal to zero or not, If the value is equal to zero, the loop ends. Else the statements in the loop are executed.
  The gcd of two numbers using recursion:

• This program is used to find the gcd of two numbers by recursively calling the function.

/ / program to find out gcd by using recursion
# include <stdio.h>
Int gcd (int a,int b);
/ / main function
Int main () {
Printf(“ Enter the two numbers : “);
Scanf(“%d %d “,&a,&b);


printf(“ The gcd of two numbers is %d ”, gcd(a,b));
return 0;
}
Int gcd (int a, int b) {
If (b == 0) {
Return a;
}
else {
return gcd (b,a%b);
} }

Output:

Enter the two numbers: 81

 153

The gcd of two numbers is 9

• In the above program, in the main function, the line gcd (int a,int b) makes the compiler go to that function.
• In the function, the line gcd ( b, a% b) line is used to call the function recursively.
• And it is essential in c language in recursive program to write a base case, this base case act as a condition and checks every time not to execute the loop infinite times.
• Here (b==0) is the base condition. If the value reaches this state, then the loop execution stops.
  Gcd of positive and negative integers:

/ * Program to find gcd of two numbers for positive and negative integers * /
#include <stdio.h>
/ / main function
Int main () {
Int a,b;
Printf(“ Enter the two numbers : “);
Scanf(“%d %d “,&a,&b);
/ / if any of the integers is negative, then the sign of integer is changed
a = ( a > 0) ? a : -a;
b = ( b > 0) ? b : -b;
while (a != b);{
If (a > b)
a= a – b;
else
b = b – a;}
Printf(“ The gcd of two numbers is %d ”, gcd);
return 0;
}

Output: Enter the two numbers: 81

- 153

The gcd of two numbers is 9

• In the above program, if any of the input integers is negative, it is changed to a positive integer by changing the sign of the integer.