C Program to find GCD of Two Numbers

How to write a c program to find GCD of two numbers using For Loop, While Loop, Functions, and Recursion.

GCD of Two Numbers

According to Mathematics, the Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides the given integer values without the remainder. For example, the GCD of two numbers in C, i.e., integers 8 and 12, is 4 because both 8 and 12 are divisible by 1, 2, and 4 (the remainder is 0), and the largest positive integer among the factors 1, 2, and 4 is 4.

The Greatest Common Divisor (GCD) is also known as the Highest Common Factor (HCF), or Greatest Common Factor (GCF), or Highest Common Divisor (HCD), or Greatest Common Measure (GCM).

C Program to find GCD of Two Numbers using For Loop

This gcd of two numbers in the C program allows the user to enter two positive integer values. Then, we are going to calculate the Highest Common Factor of those two values. Next, using the For loop, it will calculate the GCD. To find the Greatest Common Divisor, we have to pass at least one non-zero value.

#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;
}

C HCF of two numbers output

Please Enter two integer Values 
8
12
GCD of 8 and 12 is = 4

Within this example, the first programming printf statement will ask the user to enter two positive integer values.

The For loop will resist the i value, not to exceed the user-specified values. In the next line, we used the If Statement to check whether the remainder of Num1 % i and Num2 % i equal zero or not.

C Program to find GCD of Two Numbers using While Loop

This GCD of two numbers program in c allows the user to enter two positive integer values. Next, we are going to calculate the Greatest Common Measure of those two values using the While Loop.

#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;
}
C Program to find GCD of Two Numbers 2

In this program, within the while loop, we are checking whether the second value is not equal to zero or not. If it is zero, it will exit the while loop. Otherwise, it will start executing the statements inside the while loop.

C Program to find GCD of Two Numbers without using Temp

This C gcd program allows you to enter two positive integer values. Next, we are going to calculate the Greatest Common Measure of those two values without using the Temporary variable.

#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;
}

HCF of two numbers output

Please Enter two integer Values 
75
255
GCD = 15

C Program to find GCD of Two Numbers Using Functions

This C program for the gcd of two numbers allows the user to enter two positive integer values. Next, we are going to calculate the Greatest Common Divisor of those two values using Functions.

#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;
}
Please Enter two integer Values 
75
1575
GCD of 75 and 1575 is = 75

C Program to find GCD of Two Numbers using Recursion

This gcd of two numbers in the C program allows the user to enter two positive integer values. Next, we are going to calculate the Greatest Common Divisor of those two values by calling the function recursively. Please refer to Recursion for further reference.

#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);
  }
}
Please Enter two integer Values 
81
153
GCD of 81 and 153 is = 9

Within this gcd of two numbers example in c, when the compiler reaches to long gcd(long x, long y) line in the main() program, the compiler will immediately jump to the below function:

long gcd(long x, long y) {

In the above-specified function, the return gcd(y, x % y) statement will help the program call the function Recursively with the updated value. If you miss this statement in the gcd of two numbers program, after completing the first line, it will terminate.

Let’s see the If condition in gcd program. Here, if (y == 0) will check whether the number is equal to 0 or not. For Recursive functions, it is essential to place a condition before using the function recursively. Otherwise, we will end up in infinite execution (Same as Infinite Loop). Please be careful :)

Comments are closed.