C Program to Find GCD of Two Numbers

C program to find gcd of two number; Through this tutorial, we will learn how to find and print gcd of two number in c program using for loop, while loop, without temp variable, functions and recursion.

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. 

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 output 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 output 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 output 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 output 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 output of the above c program; as follows:

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

Recommended C Programs