C Program to Find GCD of Two Numbers

The greatest common divisor (GCD) of two or more numbers is the greatest common factor number that divides them, exactly. It is also called the highest common factor (HCF). For example, the greatest common factor of 15 and 10 is 5, since both the numbers can be divided by 5.

15/5 = 3

10/5 = 2

If a and b are two numbers then the greatest common divisor of both the numbers is denoted by gcd(a, b). To find the gcd of numbers, we need to list all the factors of the numbers and find the largest common factor. 

In this tutorial, i am going to show you how to find and print gcd of two number in c program using for loop, while loop, without temp variable, functions and recursion.

Programs to Find GCD of Two Numbers in C

  • C Program to find GCD of Two Numbers using For Loop
  • C Program to find GCD of Two Numbers using While Loop
  • C Program to find GCD of Two Numbers without using Temp
  • C Program to find GCD of Two Numbers Using Functions
  • C Program to find GCD of Two Numbers using Recursion

C Program to find GCD of Two Numbers using For Loop

// C program to find HCF of two numbers
#include <stdio.h>
int main()
{
    int Num1, Num2, i, GCD;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
    for(i = 1; i <= Num1 && i <= Num2; i++)
    {
        if(Num1 % i == 0 && Num2 % i == 0)
            GCD = i;
    }
    printf("GCD of %d and %d is = %d", Num1, Num2, GCD);
    return 0;
}

The result of the above c program; as follows:

Please Enter two integer Values :- 10 25
GCD of 10 and 25 is = 5

C Program to find GCD of Two Numbers using While Loop

// C program to find HCF of two numbers
#include <stdio.h>
int main()
{
    int Num1, Num2, Temp, GCD;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
    while (Num2 != 0) {
 	Temp = Num2;
 	Num2 = Num1 % Num2;
 	Num1 = Temp;
    }
    GCD = Num1;
    printf("GCD = %d", GCD);
    return 0;
}

The result of the above c program; as follows:

Please Enter two integer Values :- 15 45
GCD = 15

C Program to find GCD of Two Numbers without using Temp

#include <stdio.h>
int main()
{
    int Num1, Num2, GCD;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
	if (Num1 == 0) {
  		printf("GCD = %d", Num2);
  	}
 	while (Num2 != 0) {
    	if (Num1 > Num2) {
      		Num1 = Num1 - Num2;
    }
    	else {
      		Num2 = Num2 - Num1;
    	}
  	}
  	GCD = Num1;
    printf("GCD = %d", GCD);
    return 0;
}

The result of the above c program; as follows:

Please Enter two integer Values :- 10 25
GCD = 5

C Program to find GCD of Two Numbers Using Functions

// C program to find HCF of two numbers
#include <stdio.h>
long gcd(long x, long y);
int main()
{
    int Num1, Num2;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
    printf("GCD of %d and %d is = %d", Num1, Num2, 	gcd(Num1, Num2));
    return 0;
}
long gcd(long x, long y) 
{
	if (x == 0) {
  		return y;
  	}
 	while (y != 0) {
    	if (x > y) {
      		x = x - y;
    }
    	else {
      		y = y - x;
    	}
  	}
  	return x;
}

The result of the above c program; as follows:

Please Enter two integer Values :- 50 100
GCD of 50 and 100 is = 50

C Program to find GCD of Two Numbers using Recursion

#include <stdio.h>
long gcd(long x, long y);
int main()
{
    int Num1, Num2;
    printf("Please Enter two integer Values \n");
    scanf("%d %d", &Num1, &Num2);
    printf("GCD of %d and %d is = %d", Num1, Num2, gcd(Num1, Num2));
    return 0;
}
long gcd(long x, long y) 
{
  if (y == 0) {
  	return x;
  }
  else {
    return gcd(y, x % y);
  }
}

The result of the above c program; as follows:

Please Enter two integer Values :- 20 25
GCD of 20 and 25 is = 5

More C Programming Tutorials

Be First to Comment

Leave a Reply

Your email address will not be published.